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

Abstract

Let $G$ be a graph with vertex set $V$ and let $g,f:V\to {\mathbb{Z}}^{+}$ be two functions such that $g\le f$. We say that $G$ has all $(g,f)$-factors if $G$ has an $h$-factor for every $h:V\to {\mathbb{Z}}^{+}$ such that $g(v)\le h(v)\le f(v)$ for every $v\in V$ and ${\sum }_{v\in V}h(v)\equiv 0(\mathrm{mod}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}, \textbf{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.

References in corpus (1)

• Characterization of 1-Tough Graphs using Factors