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$
1
  • $\begingroup$ $NP$-completeness refers to the decision version of the problem. $\endgroup$ Apr 13, 2011 at 10:49

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.