7
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ (I thought this was going to be about citation metrics!) $\endgroup$ – Jeffε Jul 6 '12 at 6:15
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tyson Williams Jul 6 '12 at 17:19
  • $\begingroup$ It's the same for symmetric relations, but Feder's framework also includes asymmetric relations. $\endgroup$ – Colin McQuillan Jul 6 '12 at 23:07
  • $\begingroup$ 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. $\endgroup$ – Colin McQuillan Jul 6 '12 at 23:15
  • $\begingroup$ Excellent, I wasn't expecting to hear about work on the asymmetric case. Is there work on the degree-bounded case as well? $\endgroup$ – Tyson Williams Jul 7 '12 at 14:29
  • $\begingroup$ 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. $\endgroup$ – Colin McQuillan Jul 9 '12 at 10:08
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Tyson Williams Jul 6 '12 at 13:53
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Jul 7 '12 at 2:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.