<p>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$?"</p>

<p>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.</p>

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

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

CC BY-SA 3.0
2013-12-13T07:58:54.863Z
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
CC BY-SA 3.0
2013-12-14T04:01:49.153Z
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
CC BY-SA 3.0
2013-12-15T21:13:10.843Z
So this is a Cook reduction. Right? Also, I guess two times are enough.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-17T18:42:08.503Z
Yes, two times are enough actually.  Note that the reduction preserves planarity and biparteness.
Andrew D. King
CC BY-SA 3.0
2013-12-12T19:10:42.047Z
2013-12-12T19:16:30.383Z
2013-12-12T19:16:30.383Z
Andrew D. King
<p>Petersen's theorem states that a bridgeless cubic graph contains a perfect matching (1-factor). Motivated by this question, <a href="https://cstheory.stackexchange.com/questions/6107/complexity-of-finding-2-vertex-disjoint-v-2-cycles-in-cubic-graphs">Complexity of finding 2 vertex-disjoint (|V|/2)-cycles in cubic graphs?</a> 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$).</p>

<blockquote>
  <p>Is this problem solvable in P-time? Is it $NP$-complete?</p>
</blockquote>

<p>The input is connected bridgeless cubic graph.</p>

CC BY-SA 3.0
2013-12-11T16:29:34.987Z
Restricted to bridgeless cubic graphs?
David Richerby
CC BY-SA 3.0
2013-12-11T16:56:05.017Z
Yes David. Input is restricted to bridgeless cubic graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-12-11T19:09:36.907Z
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
CC BY-SA 3.0
2013-12-11T20:24:19.213Z
@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
CC BY-SA 3.0
2013-12-12T01:39:14.760Z
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
CC BY-SA 3.0
2013-12-12T02:48:48.430Z
@DavidEppstein  Yes I mean 2-edge-connected graph. Also the input is connected bridgeless cubic graph. So yes, that is a cheat :) What is your guess? Do you think it is NPC and why?
Mohammad Al-Turkistany
<cc.complexity-theory><graph-theory>
Finding balanced disjoint cycles in bridgeless cubic graphs
Mohammad Al-Turkistany
# Finding balanced disjoint cycles in bridgeless cubic graphs

(Asked by: username_0 on 2013-12-11)

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?](https://cstheory.stackexchange.com/questions/6107/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.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: Restricted to bridgeless cubic graphs?  
> **username_0**: Yes David. Input is restricted to bridgeless cubic graphs.  
> **username_2**: 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?  
> **username_0**: @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.  
> **username_2**: 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.  
> **username_0**: @DavidEppstein  Yes I mean 2-edge-connected graph. Also the input is connected bridgeless cubic graph. So yes, that is a cheat :) What is your guess? Do you think it is NPC and why?  

---

## 1 answers

### Answer by username_3 on 2013-12-12. Score: 5 | Accepted 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?

> **Comments:**
> **username_0**: 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?  
> **username_3**: 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.  
> **username_0**: So this is a Cook reduction. Right? Also, I guess two times are enough.  
> **username_3**: Yes, two times are enough actually.  Note that the reduction preserves planarity and biparteness.  

---

