# What is known about the H-factor problem?

## 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.

• (I thought this was going to be about citation metrics!) Jul 6, 2012 at 6:15

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.

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.

• Yes, with the constant relations and a constraint containing a length $k$ gap, one can construct the arity $k+1$ equality constraint and thus all arity equalities provided $k>1$. How is Feder's cited paper a big generalisation if it follows from the tractability result I cited combined with your equality construction observation? Feder doesn't cite any papers about graph fractors and claims that his graph constraint satisfaction framework is new even though it is the same as the $\mathcal{H}$-factor problem. It seems like Feder reproved an existing result without knowing it. Jul 6, 2012 at 17:19
• It's the same for symmetric relations, but Feder's framework also includes asymmetric relations. Jul 6, 2012 at 23:07
• Also, I think it shouldn't be too difficult to get rid of the assumption on constant relations. You might want to just work this out yourself though. Things seem to get much more complicated if you add degree bounds to the input graph. Jul 6, 2012 at 23:15
• Excellent, I wasn't expecting to hear about work on the asymmetric case. Is there work on the degree-bounded case as well? Jul 7, 2012 at 14:29
• From the CSP point of view the degrees are always restricted because the degree of the vertex is the arity of the constraint. For your specific problem I now think upper-bounding the degree doesn't create any problems - see my edit. Jul 9, 2012 at 10:08

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$-hard when parameterized by treewidth, even when the graph is bipartite and one partite set uniformly has $H_{v}=\{1\}$ . 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.

• Thanks for your answer, in which I added some links to references. I am aware of the $r$-factor (which I know as $k$-factor) and $f$-factor problems. After some Googling, my understanding of the $b$-factor problem is that $b : V \to \mathbb{N}$ defines $H_v$ to be $\{1,...,b(v)\}$ (that is, $b$ is a bound on the degree, except that degree 0 is not allowed). As you said, all of these problems are tractable. Indeed, they are all special cases of the tractability result that I quoted (i.e. no $H_v$ contains two consecutive gaps). Jul 6, 2012 at 13:53
• You can also stick a lower bound in for the PERFECT-$b$-MATCHING problem, so $H_{v} = \{c(v),\ldots,b(v)\}$, but these are indeed all special cases of Cornuejol's result (it's a very sharp result!). If you allow (induced) proper subgraphs, then you get quite different results - of course these are not quite factors anymore. Jul 7, 2012 at 2:11