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 perfect matching).

I conjecture that it is hard to recognize bridgeless cubic graphs when restricting cycles lengths in the 2-factor. I conjecture that it is $NP$-complete to decide the existence of restricted 2-factor in a bridgeless cubic graph.

Restricted 2-factor problem:

Input: connected bridgeless cubic graph.

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

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). Deciding the existence of $C_4$-free 2-factor is an open problem.

Is this a known result? Or is there a counter-example to this conjecture?

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

  • 1
    $\begingroup$ Do you know anything about the same problem for $C_3$-free factors? $\endgroup$ – Ilya Bogdanov Oct 22 '14 at 13:10
  • $\begingroup$ No, I am not aware of such result. $\endgroup$ – Mohammad Al-Turkistany Oct 22 '14 at 17:16

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.