# Finding balanced disjoint cycles in bridgeless cubic graphs

Petersen's theorem states that a bridgeless cubic graph contains a perfect matching (1-factor). Motivated by this question, Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs? I am interested in the problem of deciding the existence of perfect matching $M$ such that removing the edges of $M$ leaves two node-disjoint cycles of equal cardinality (each cycle has size $|V|/2$).

Is this problem solvable in P-time? Is it $NP$-complete?

The input is connected bridgeless cubic graph.

• Restricted to bridgeless cubic graphs? Dec 11, 2013 at 16:29
• Yes David. Input is restricted to bridgeless cubic graphs. Dec 11, 2013 at 16:56
• Do you have either a reason for expecting anything but NP-completeness as the answer, or a reason why an NP-completeness proof would actually be interesting? Dec 11, 2013 at 19:09
• @DavidEppstein I expect NP-completeness because of the special structure of $E-M$. Also, I know that Hamiltonian cycle is NP-complete on bridgeless cubic graphs. Dec 11, 2013 at 20:24
• Also presumably you mean 2-edge-connected when you say bridgeless. If you take two disjoint copies of a hard instance for Hamiltonian cycle on bridgeless cubic graphs then the result is hard for your problem and has no bridges. But maybe you would consider that a cheat. Dec 12, 2013 at 1:39

This is NP-complete; reduction from the question, "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?"
Construct $G$ as follows. Take two copies of $H-e$, denoting the endpoints of $e$ in the first copy $v_1$, $u_1$ and denoting the endpoints of $e$ in the second copy $v_2$, $u_2$. Add edges $e_v$ between $v_1$ and $v_2$, and $e_u$ between $u_1$ and $u_2$. Observe that $G$ is 2-edge-connected.
Any cycle of $G$ contains both or neither of $e_v$ and $e_u$, since these edges form an edge cut. Thus if $G$ has two vertex-disjoint cycles of length $|V(H)|$, they must each lie in a separate copy of $H$. Such cycles exist precisely if $H$ contains a Hamiltonian cycle avoiding $e$.
• Just to clarify, To prove the $NP$-completeness of "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle avoiding a given edge $e$?", Are you reducing from "Given a cubic graph $G$ and an edge $e$ in $G$, is there a Hamiltonian cycle through $e$"? problem? Dec 13, 2013 at 7:58
• I am reducing from "Does a 2-edge-connected cubic graph $H$ contain a Hamiltonian cycle?" To solve this, solve the edge-specified problem three times: once for each edge around a vertex. Dec 14, 2013 at 4:01