Petersen's Theorem states that every cubic, bridgeless graph $G(V, E)$ contains a 2-factor $F$ (and therefore a perfect matching $E-F$). Alternatively, 2-factor is a set of vertex disjoint cycles that cover $V$. I'm interested in the computational properties of 2-factors in connected bridgeless cubic graphs. I conjecture that every non-trivial property of two-factors in connected bridgeless cubic graphs is intractable.

There are two parameters of two-factor: the number of disjoint cycles and the size of each cycle. So, it seems that restricting cycles sizes and/or the number of cycles in the 2-factor would make the decision problem of deciding the existence of restricted 2-factor is $NP$-complete. For instance, I conjecture the following decision problem is NP-complete: Given connected bridgeless cubic graph, decide whether it contains 2-factor such that cycles sizes are between two integers $n$ and $m$.

Non-trivial property in this context means a restriction on the parameters of 2-factor (in connected bridgeless cubic graph ) which partitions the class of connected bridgeless cubic graphs into two infinite sets. Therefore, there is infinite set of connected bridgeless cubic graphs with their 2-factor satisfying the property and infinite set not satisfying the property. I am aware of several $NP$-complete properties of 2-factors in connected bridgeless cubic graphs. For instance, Deciding the existence of connected 2-factor, even 2-factor, and odd 2-factor are all $NP$-complete problems.

When does such non-trivial property of 2-factor become $NP-complete? When does it become polynomial-time decidable?

This is an improved version of a post originally posted on TCS SE.

  • $\begingroup$ it would be helpful/more complete to cite ref(s) for the last assertions on NP completeness of 2-factor problems. $\endgroup$ – vzn Feb 6 '14 at 1:36
  • $\begingroup$ ? & curious why posting here, it seems clearly a tcs.se level question... also better to cite the tcs.se Q $\endgroup$ – vzn Feb 6 '14 at 17:44
  • 1
    $\begingroup$ Because of TCS's tough standards ;) $\endgroup$ – Mohammad Al-Turkistany Feb 6 '14 at 17:48
  • $\begingroup$ not mandatory of course but an example would be really helpful for this assertion "Alternatively, 2-factor is a set of vertex disjoint cycles that cover V"...having trouble picturing that on a cubic graph... isnt a 2-factor also 2-regular? $\endgroup$ – vzn Feb 6 '14 at 17:57
  • $\begingroup$ the question needs to be clarified a bit to be more self-contained, it seems like the 2-factor is not given in the problem, right? the problem is more like "does a 2-factor exist with property [x]" right? $\endgroup$ – vzn Feb 6 '14 at 18:07

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.