6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Restricted to bridgeless cubic graphs? $\endgroup$ – David Richerby Dec 11 '13 at 16:29
  • $\begingroup$ Yes David. Input is restricted to bridgeless cubic graphs. $\endgroup$ – Mohammad Al-Turkistany Dec 11 '13 at 16:56
  • $\begingroup$ 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? $\endgroup$ – David Eppstein Dec 11 '13 at 19:09
  • $\begingroup$ @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. $\endgroup$ – Mohammad Al-Turkistany Dec 11 '13 at 20:24
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Dec 12 '13 at 1:39
4
$\begingroup$

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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.