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.

$\endgroup$
  • $\begingroup$ $NP$-completeness refers to the decision version of the problem. $\endgroup$ – Mohammad Al-Turkistany Apr 13 '11 at 10:49

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.