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

arXiv1702.05874MaRDI QIDQ6283377FDOQ6283377

Authors: Hongliang Lü 

Publication date: 20 February 2017

Abstract: Let $G$ be a graph with vertex set $V$ and let $g,f:Vightarrowmathbb{Z}^{+}$ be two functions such that $glef$. We say that $G$ has all $(g,f)$-factors if $G$ has an $h$-factor for every $h:Vightarrowmathbb{Z}^{+}$ such that $g(v)leh(v)lef(v)$ for every $vinV$ and $su{m}_{vinV}h(v)equiv0pmod2$. 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}, extbf{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.

This page was built for publication: The Complexity of All $(g,f)$-Factor Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6283377)