3
$\begingroup$

A 2-factor of graph $G(V, E)$ is a set of vertex-disjoint cycles that cover $V$. It is known 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 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Feb 11 '14 at 17:25
  • $\begingroup$ 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|} $\endgroup$ – daniello Apr 3 '17 at 22:21

Your Answer

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

Browse other questions tagged or ask your own question.