Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
$NP$-completeness refers to the decision version of the problem. –  Mohammad Al-Turkistany Apr 13 '11 at 10:49
add comment

Know someone who can answer? Share a link to this question via email, Google+, Twitter, or Facebook.

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.