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

Improve this question
$\endgroup$
6
  • $\begingroup$ Restricted to bridgeless cubic graphs? $\endgroup$
    – David Richerby
    Commented Dec 11, 2013 at 16:29
  • $\begingroup$ Yes David. Input is restricted to bridgeless cubic graphs. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 11, 2013 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
    Commented Dec 11, 2013 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
    Commented Dec 11, 2013 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
    Commented Dec 12, 2013 at 1:39

1 Answer 1

Reset to default
5
$\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?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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