What is known about the H-factor problem?

Question

Background

The $\mathcal{H}$-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows:

Given a graph $G=(V,E)$ and a set $H_v \subseteq \mathbb{N}$ for each vertex $v \in V$, does $G$ contain a spanning subgraph $F$ such that $\operatorname{deg}_F(v) \in H_v$ for all $v \in V$?

(I would also say that $H_v \in \mathcal{H}$ for all $v \in V$, but I have never seen it stated this way. Thus, the $\mathcal{H}$-factor problem is defined by $\mathcal{H}$ and the input is a graph $G=(V,E)$ and a mapping $f : V \to \mathcal{H}; v \mapsto H_v$.)

A spanning subgraph is also known as a factor, hence the name. This framework of problems captures many classic problems. For example, when $H_v = \{1\}$ for all $v \in V$, the problem is to determine if $G$ contains a perfect matching, also called a 1-factor.

Question

What is currently known about the complexity of this problem for different $\mathcal{H}$?

What about the special case when $\mathcal{H}$ is a singleton set (so $H_v$ is the same for all $v \in V$)?

Strongest Results I Know

Tractability: If each set in $\mathcal{H}$ does not contain two consecutive gaps, then the $\mathcal{H}$-factor problem is in P (Cornuejols 1988). A integer $h$ is a gap in $H \subseteq \mathbb{N}$ if $h \not\in H$ but $H$ contains an element less than $h$ and an element greater than $h$.

Hardness: There exist some $\mathcal{H}$ such that the $\mathcal{H}$-factor problem is NP-hard (Lovasz 1972).

See (Szabo 2004) for a modern reference that cites these two results.

Answer 1

This can be considered as a type of read-twice constraint satisfaction problem. Unless I'm mistaken, it is quite easy to construct an "equality" gadget whenever $H$ has a double gap, if you allow constant constraints (requiring an edge to be in or out). Then you can use Schaeffer's Boolean CSP classification. So the problem then comes down to whether constants are important.

There is a big generalisation:

"Fanout limitations on constraint systems", Tomás Feder, Theoretical Computer Science, Volume 255, Issue 1-2, March 28, 2001, Pages 281 - 293.

http://www.sciencedirect.com/science/article/pii/S0304397599002881

Basically, for constraint languages $\Gamma$ (i.e. a finite set of Boolean relations) such that $\Gamma$ contains the constant relations $\{(0)\}$ and $\{(1)\}$, Feder considers the following problem: the input is a conjunction of constraints of the form $(v_{i_1},\dots,v_{i_k})\in R$ for some $R\in\Gamma$, such that each variable appears at most twice, and we ask if there is a satisfying assignment. Feder shows that if the constraint language contains a non-delta-matroid, the problem is equivalent to the unbounded-degree CSP. A set $H$ that has gaps (i.e. whenever Cornuejols' algorithm doesn't work) is a non-delta-matroid.

You can reduce read-once-or-twice to read-twice by doubling the instance and identifying the variables that were read exactly once.

Added later:

For your particular problem, I believe the assumption about constants is easy to get around. Let $\mathbb{N}=\{0,1,2,\dots\}$. For all $\mathcal{H}\subseteq 2^{\mathbb{N}}$ and all $d\in\mathbb{N}\cup\{\infty\}$, the following problem is either in P or NP-complete.

• Name: Factor$(\mathcal{H},d)$.
• Input: a simple graph $G$ of maximum degree at most $d$, and a set $H_v\in\mathcal{H}$ for each $v$.
• Output: Is there a spanning subgraph of $G$ in which the degree of each vertex $v$ is in $H_v$?

Sketch proof:

1. If for all $H\in\mathcal{H}$, there are no gaps of length $\geq 2$ in $H\cap\{0,\dots,d\}$, the problem is tractable by Cornuejols' algorithm.
2. If for $H\in\mathcal{H}$ we have $0\in H$ or $H\cap\{0,\dots,d\}=\emptyset$, the problem is trivial: every graph has a 0-factor so all inputs are accepted.
3. Otherwise, since (2.) fails, there is a non-empty set $H\in\mathcal{H}$ with $0\notin H$ and $\min(H)\leq d$. So if a vertex $v$ has degree $\min(H)$ and $H_v$, then all its edges must be in. So we can force edges to be in, and simulate constants, and appeal to Feder's result.

This kind of gadgetry fails if we restrict the degrees of the input graph. For example let $H=\{1,4\}\subset\{0,1,2,3,4,5\}$, and restrict the inputs to graphs that are regular of degree five. By symmetry, one cannot simulate constants.

Answer 2

Assuming you want to stick to spanning subgraphs, $r$-FACTOR is the version where you have each vertex with $H_{v} = \{r\}$, a slightly more general version is $f$-FACTOR, where each vertex has a singleton for its degree target list, but it can be different for each vertex. Both of these are in P, along with the (PERFECT-)$b$-MATCHING problem. Tutte 1 gives the algorithm, but getting hold of that paper might prove tricky. A later publication of Tutte's 2 might be more readily available. Korte & Vygen 3 is definitely easier to find, and they have quite a bit of detail on variants and the P-time algorithms.

A clear parameterized result is that GENERAL FACTOR is $W[1]$-hard when parameterized by treewidth, even when the graph is bipartite and one partite set uniformly has $H_{v}=\{1\}$ [4]. If you want to go down the parameterized complexity road further, then I can shamelessly plug my thesis (my website is linked off my profile), but these results are probably too far from what you want - they're more related to editing versions of the problem, where we only want to change the graph a small amount to get the factor.

1. W. T. Tutte. A short proof of the factor theorem for finite graphs. Canad. J. Math., 6:347–352, 1954.

2. W. T. Tutte. Graph factors. Combinatorica, 1(1):79–97, 1981.

3. B. Korte and J. Vygen. Combinatorial Optimization, volume 21 of Algorithms and Combinatorics. Springer, Berlin, fourth edition, 2008.

4. M. Samer and S. Szeider. Tractable cases of the extended global cardinality constraint. In Computing: The Australasian Theory Symposium (CATS’08), volume 77 of CRPIT, pages 67–74. ACS, 2008.