# 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? – David Richerby Dec 11 '13 at 16:29
• Yes David. Input is restricted to bridgeless cubic graphs. – Mohammad Al-Turkistany Dec 11 '13 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? – David Eppstein Dec 11 '13 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. – Mohammad Al-Turkistany Dec 11 '13 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. – David Eppstein Dec 12 '13 at 1:39

## 1 Answer

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$.

Edit: Am I missing something obvious, or is the question of finding a good perfect matching clearly equivalent to finding the two long cycles?

• 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? – Mohammad Al-Turkistany Dec 13 '13 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. – Andrew D. King Dec 14 '13 at 4:01
• So this is a Cook reduction. Right? Also, I guess two times are enough. – Mohammad Al-Turkistany Dec 15 '13 at 21:13
• Yes, two times are enough actually. Note that the reduction preserves planarity and biparteness. – Andrew D. King Dec 17 '13 at 18:42