<p>Assuming you want to stick to <i>spanning</i> 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 <b>P</b>, along with the (PERFECT-)$b$-MATCHING problem. Tutte <a href="http://cms.math.ca/10.4153/CJM-1954-033-3" rel="nofollow">1</a> gives the algorithm, but getting hold of that paper might prove tricky. A later publication of Tutte's <a href="http://rads.stackoverflow.com/amzn/click/3540431543" rel="nofollow">2</a> might be more readily available. Korte &amp; Vygen <a href="http://www.kr.tuwien.ac.at/drm/szeider/abstract39" rel="nofollow">3</a> is definitely easier to find, and they have quite a bit of detail on variants and the <b>P</b>-time algorithms.</p>

<p>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.</p>

<ol>
<li><p><a href="http://cms.math.ca/10.4153/CJM-1954-033-3" rel="nofollow">W. T. Tutte. A short proof of the factor theorem for finite graphs. Canad. J.</a>
Math., 6:347–352, 1954.</p></li>
<li><p>W. T. Tutte. Graph factors. Combinatorica, 1(1):79–97, 1981.</p></li>
<li><p><a href="http://rads.stackoverflow.com/amzn/click/3540431543" rel="nofollow">B. Korte and J. Vygen. Combinatorial Optimization, volume 21 of Algorithms
and Combinatorics. Springer, Berlin, fourth edition, 2008.</a></p></li>
<li><p><a href="http://www.kr.tuwien.ac.at/drm/szeider/abstract39" rel="nofollow">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.</a></p></li>
</ol>

CC BY-SA 3.0
2012-07-06T13:53:03.463Z
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).
Tyson Williams
CC BY-SA 3.0
2012-07-07T02:11:16.387Z
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.
Luke Mathieson
CC BY-SA 3.0
2012-07-06T05:49:32.290Z
2012-07-06T15:01:16.560Z
2012-07-06T15:01:16.560Z
Luke Mathieson
<p>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.</p>

<p>There is a big generalisation:</p>

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

<p><a href="http://www.sciencedirect.com/science/article/pii/S0304397599002881" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0304397599002881</a></p>

<p>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.</p>

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

<p><strong>Added later:</strong></p>

<p>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.</p>

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

<p>Sketch proof:</p>

<ol>
<li>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.</li>
<li>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.</li>
<li>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.</li>
</ol>

<p>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.</p>

CC BY-SA 3.0
2012-07-06T17:19:15.563Z
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.
Tyson Williams
CC BY-SA 3.0
2012-07-06T23:07:35.813Z
It's the same for symmetric relations, but Feder's framework also includes asymmetric relations.
Colin McQuillan
CC BY-SA 3.0
2012-07-06T23:15:59.033Z
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.
Colin McQuillan
CC BY-SA 3.0
2012-07-07T14:29:22.603Z
Excellent, I wasn't expecting to hear about work on the asymmetric case. Is there work on the degree-bounded case as well?
Tyson Williams
CC BY-SA 3.0
2012-07-09T10:08:16.810Z
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.
Colin McQuillan
CC BY-SA 3.0
2012-07-06T16:11:18.187Z
2012-07-09T15:26:48.580Z
2012-07-09T15:26:48.580Z
Colin McQuillan
<h2>Background</h2>
<p>The <span class="math-container">$\mathcal{H}$</span>-factor problem (a.k.a. the degree prescribed factor problem, or the degree prescribed subgraph problem) is defined as follows:</p>
<p>Given a graph <span class="math-container">$G=(V,E)$</span> and a set <span class="math-container">$H_v \subseteq \mathbb{N}$</span> for each vertex <span class="math-container">$v \in V$</span>, does <span class="math-container">$G$</span> contain a spanning subgraph <span class="math-container">$F$</span> such that <span class="math-container">$\operatorname{deg}_F(v) \in H_v$</span> for all <span class="math-container">$v \in V$</span>?</p>
<p>(I would also say that <span class="math-container">$H_v \in \mathcal{H}$</span> for all <span class="math-container">$v \in V$</span>, but I have never seen it stated this way. Thus, the <span class="math-container">$\mathcal{H}$</span>-factor problem is defined by <span class="math-container">$\mathcal{H}$</span> and the input is a graph <span class="math-container">$G=(V,E)$</span> and a mapping <span class="math-container">$f : V \to \mathcal{H}; v \mapsto H_v$</span>.)</p>
<p>A spanning subgraph is also known as a <a href="http://en.wikipedia.org/wiki/1-factor" rel="nofollow noreferrer">factor</a>, hence the name. This framework of problems captures many classic problems. For example, when <span class="math-container">$H_v = \{1\}$</span> for all <span class="math-container">$v \in V$</span>, the problem is to determine if <span class="math-container">$G$</span> contains a perfect matching, also called a 1-factor.</p>
<h2>Question</h2>
<p>What is currently known about the complexity of this problem for different <span class="math-container">$\mathcal{H}$</span>?</p>
<p>What about the special case when <span class="math-container">$\mathcal{H}$</span> is a singleton set (so <span class="math-container">$H_v$</span> is the same for all <span class="math-container">$v \in V$</span>)?</p>
<h2>Strongest Results I Know</h2>
<p>Tractability:
If each set in <span class="math-container">$\mathcal{H}$</span> does not contain two consecutive gaps, then the <span class="math-container">$\mathcal{H}$</span>-factor problem is in P (Cornuejols 1988). A integer <span class="math-container">$h$</span> is a gap in <span class="math-container">$H \subseteq \mathbb{N}$</span> if <span class="math-container">$h \not\in H$</span> but <span class="math-container">$H$</span> contains an element less than <span class="math-container">$h$</span> and an element greater than <span class="math-container">$h$</span>.</p>
<p>Hardness: There exist some <span class="math-container">$\mathcal{H}$</span> such that the <span class="math-container">$\mathcal{H}$</span>-factor problem is NP-hard (Lovasz 1972).</p>
<p>See (<a href="http://www.cs.elte.hu/egres/www/tr-04-19.html" rel="nofollow noreferrer">Szabo 2004</a>) for a modern reference that cites these two results.</p>

CC BY-SA 3.0
2012-07-06T06:15:50.557Z
(I thought this was going to be about citation metrics!)
Jeffε
<cc.complexity-theory><reference-request><graph-theory><np-hardness><csp>
What is known about the H-factor problem?
Tyson Williams
# What is known about the H-factor problem?

(Asked by: username_0 on 2012-07-06)

## 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](http://en.wikipedia.org/wiki/1-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](http://www.cs.elte.hu/egres/www/tr-04-19.html)) for a modern reference that cites these two results.

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness, csp

> **Comments:**
> **username_1**: (I thought this was going to be about citation metrics!)  

---

## 2 answers

### Answer by username_3 on 2012-07-06. Score: 6 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_3**: It's the same for symmetric relations, but Feder's framework also includes asymmetric relations.  
> **username_3**: 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.  
> **username_0**: Excellent, I wasn't expecting to hear about work on the asymmetric case. Is there work on the degree-bounded case as well?  
> **username_3**: 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.  

---

### Answer by username_2 on 2012-07-06. Score: 4

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](http://cms.math.ca/10.4153/CJM-1954-033-3) gives the algorithm, but getting hold of that paper might prove tricky. A later publication of Tutte's [2](http://rads.stackoverflow.com/amzn/click/3540431543) might be more readily available. Korte & Vygen [3](http://www.kr.tuwien.ac.at/drm/szeider/abstract39) 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.](http://cms.math.ca/10.4153/CJM-1954-033-3)
   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.](http://rads.stackoverflow.com/amzn/click/3540431543)
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.](http://www.kr.tuwien.ac.at/drm/szeider/abstract39)

> **Comments:**
> **username_0**: 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).  
> **username_2**: 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.  

---

