The Complexity of All $(g,f)$-Factor Problem

Let $G$ be a graph with vertex set $V$ and let $g, f : V\rightarrow $\mathbb{Z}$^+$betwofunctionssuchthat$g\le f$\mathrm{.}Wesaythat$G$hasall$(g, f )$-factorsif$G$hasan$h$-factorforevery$h: V\rightarrow $\mathbb{Z}$^+$suchthat$g(v)\le h(v)\le f (v)$forevery$v\in V$and$\sum_{v\in{V}}h(v)\equiv 0\pmod 2$. Two decades ago, Niessen derived from Tutte’s $f$-factor theorem a similar characterization for the property of graphs having all $(g,f)$-factors and asked whether there is a polynomial time algorithm for testing whether a graph $G$ has all $(g,f)$-factors (A characterization of graphs having all $(g,f)$-Factors, \emph{J. Combin. Theory, Ser. B}, $\mathbf{\text{72}}$ (1998), 152–156). In this paper, we show that it is NP-hard to determine whether a graph $G$ has all $(g,f)$-factors, which gives a negative answer to the question of Niessen.