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