<p>A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is <a href="http://en.wikipedia.org/wiki/Petersen&#39;s_theorem" rel="nofollow noreferrer">known</a> that every connected bridgeless cubic graph contains a 2-factor (and a disjoint perfect matching). I'm interested in the computational properties of 2-factors in connected bridgeless cubic graphs. </p>

<p>There are two parameters of two-factor: the number of disjoint-cycles and the size of each cycle. It seems that restricting cycles sizes and/or the number of cycles in the 2-factor makes the following decision problem $NP$-complete. The problem is to decide the existence of restricted 2-factor in the specified class of graphs. </p>

<p><strong>Restricted 2-factor problem</strong>:</p>

<p><strong>Input</strong>: connected bridgeless cubic graph.</p>

<p><strong>Output</strong>: Decide whether there is a 2-factor such that forbidden lengths of the cycles of the 2-factor form a proper non-empty subset of $N=\{5, 6, 7, ..., |V|\}$.</p>

<p>Such decomposition must partition the class of connected bridgeless cubic graphs into two infinite sets. That means, there is infinite set of connected bridgeless cubic graphs with such restricted 2-factor and infinite set not satisfying the above property. </p>

<p>I conjecture that deciding the existence of such restricted 2-factor in connected bridgeless cubic graph is $NP$-complete.</p>

<p>I am aware of several $NP$-complete decomposition problems with restricted 2-factor in connected bridgeless cubic graphs that support the conjecture. For instance, Deciding the existence of connected 2-factor, even 2-factor, and odd 2-factor are all $NP$-complete problems. In general graphs,  <a href="http://www.sciencedirect.com/science/article/pii/0012365X80900023" rel="nofollow noreferrer">Papadimitriou</a> showed that deciding the existence of $C_k$-free 2-factor is $NP$-complete when $k \ge 5$  (A 2-factor is $C_k$-free if it contains no cycles of length $k$ or less). Also, deciding the existence of $C_4$-free 2-factor is an open problem.</p>

<blockquote>
  <p>Is there a counter-example to the conjecture? </p>
</blockquote>

<p>A counter-example is a polynomial-time solvable decomposition decision problem where the forbidden lengths of the 2-factor cycles form a proper non-empty subset of $N=\{5, 6, 7, ..., |V| \}$.</p>

<p>This is motivated by my post on <a href="https://cs.stackexchange.com/questions/20203/intractable-properties-of-two-factor-in-connected-bridgeless-cubic-graphs">CS SE</a>.</p>

CC BY-SA 3.0
2014-02-11T17:25:54.943Z
This a nice reference for general graphs: P. Hell, D.G. Kirkpatrick, J. Kratochvil, I. Kriz, On restricted two-factors, SIAM J. Discrete Math. 4 (1988) 472–
484. Also, the problem is known as the restricted cycle cover problem.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-04-03T22:21:07.907Z
Isn't it polynomial time for N = {|V-1|} because no cycle cover will ever contain a cycle of length |V-1|? If so the problem becomes interesting again for proper non empty subsets of {5...|V|-3,|V|}
daniello
<cc.complexity-theory><graph-theory>
Intractability of restricted decomposition of connected bridgeless cubic graphs
Mohammad Al-Turkistany
# Intractability of restricted decomposition of connected bridgeless cubic graphs

(Asked by: username_0 on 2014-02-11)

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is [known](http://en.wikipedia.org/wiki/Petersen's_theorem) that every connected bridgeless cubic graph contains a 2-factor (and a disjoint perfect matching). I'm interested in the computational properties of 2-factors in connected bridgeless cubic graphs.

There are two parameters of two-factor: the number of disjoint-cycles and the size of each cycle. It seems that restricting cycles sizes and/or the number of cycles in the 2-factor makes the following decision problem $NP$-complete. The problem is to decide the existence of restricted 2-factor in the specified class of graphs.

**Restricted 2-factor problem**:

**Input**: connected bridgeless cubic graph.

**Output**: Decide whether there is a 2-factor such that forbidden lengths of the cycles of the 2-factor form a proper non-empty subset of $N=\{5, 6, 7, ..., |V|\}$.

Such decomposition must partition the class of connected bridgeless cubic graphs into two infinite sets. That means, there is infinite set of connected bridgeless cubic graphs with such restricted 2-factor and infinite set not satisfying the above property.

I conjecture that deciding the existence of such restricted 2-factor in connected bridgeless cubic graph is $NP$-complete.

I am aware of several $NP$-complete decomposition problems with restricted 2-factor in connected bridgeless cubic graphs that support the conjecture. For instance, Deciding the existence of connected 2-factor, even 2-factor, and odd 2-factor are all $NP$-complete problems. In general graphs, [Papadimitriou](http://www.sciencedirect.com/science/article/pii/0012365X80900023) showed that deciding the existence of $C\_k$-free 2-factor is $NP$-complete when $k \ge 5$ (A 2-factor is $C\_k$-free if it contains no cycles of length $k$ or less). Also, deciding the existence of $C\_4$-free 2-factor is an open problem.

> Is there a counter-example to the conjecture?

A counter-example is a polynomial-time solvable decomposition decision problem where the forbidden lengths of the 2-factor cycles form a proper non-empty subset of $N=\{5, 6, 7, ..., |V| \}$.

This is motivated by my post on [CS SE](https://cs.stackexchange.com/questions/20203/intractable-properties-of-two-factor-in-connected-bridgeless-cubic-graphs).

**Tags:** cc.complexity-theory, graph-theory
> **Comments:**
> **username_0**: This a nice reference for general graphs: P. Hell, D.G. Kirkpatrick, J. Kratochvil, I. Kriz, On restricted two-factors, SIAM J. Discrete Math. 4 (1988) 472– 484. Also, the problem is known as the restricted cycle cover problem.  
> **username_1**: Isn't it polynomial time for N = {|V-1|} because no cycle cover will ever contain a cycle of length |V-1|? If so the problem becomes interesting again for proper non empty subsets of {5...|V|-3,|V|}  

---

## 0 answers

