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.