2
$\begingroup$

Finding a connected 2-factor that contains every node in cubic graphs is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding vertex disjoint 2-factors with equal cardinality in cubic graphs.

I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding vertex disjoint 2-factors with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?

Providing references is highly appreciated.

Improve this question
$\endgroup$
1
  • $\begingroup$ $NP$-completeness refers to the decision version of the problem. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Apr 13, 2011 at 10:49

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .