<p>I assume, as stated in the comments, that the problem is to find a 2-factor with two cycles of length $|V|/2$ each in a cubic graph.
This problem is NP-complete:</p>

<p>1) HC in cubic graphs is NP-complete.</p>

<p>2) The following problem HC' is also NP-complete: Given a cubic graph $G$ and an edge $e$
in $G$, is there a Hamiltonian cycle through $e$. We can reduce HC to it: Given a graph $G$, replace one arbitrary vertex (left hand side) by a triangle with another vertex in it (right hand side):</p>

<p><img src="https://i.sstatic.net/bacge.jpg" alt="enter image description here"></p>

<p>Call this new graph $G'$.
$G'$ is Hamiltonian iff $G$ is. Furthermore, if $G'$ is Hamiltonian, then for any red edge, there is a Hamiltonian cycle that contains this red edge. (Without the vertex in the middle, every Hamiltonian cycle contains two green edges and any green edge can then be replaced by two red ones.) The reduction from HC to HC' maps a cubic graph $G$ to $G'$ together with any red ege.</p>

<p>3) Finally, we reduce HC' to the problem of the question. Given an instance
$(G,e)$, we create two copies of $G$, subdivide $e$ in each copy and connected the two vertices that subdivide the two copies by a new edge $f$. This edge $f$ is a bridge in the new graph. If $G$ has a Hamiltonian cycle through $e$, then the new graph has a 2-factor consisting of two cycles of the same size.
Conversely, if the new graph has such a 2-factor, then it cannot use $f$. Therefore, it splits into two Hamiltonian cycles of the two copies. Since in these copies, the vertex subdividing $e$ has degree two, we get a Hamiltonian cycle of $G$ that contains $e$.</p>

CC BY-SA 3.0
2011-05-04T11:44:24.667Z
Nice reduction. And it also answers the question under planarity and bipartiteness assumptions, since HC remains hard in that setting.
Anthony Labarre
CC BY-SA 3.0
2011-05-04T13:49:10.680Z
Planarity yes, but bipartiteness no, the reduction creates a triangle.
5501
CC BY-SA 3.0
2011-05-04T13:57:13.820Z
Oops, sorry, you are right.
Anthony Labarre
CC BY-SA 3.0
2011-05-05T16:21:15.780Z
@5501, Thanks, really nice. However, I'll wait for the cubic planar bipartite case.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-05-09T12:00:39.560Z
@Mohammad Al-Turkistany: Suggestion (haven't checked): replace a vertex with [$BW_3$](http://www.graphclasses.org/images/g_BW3.gif) instead of the above construction; the three vertices of degree 2 in that subgraph will play the role of the vertices of the triangle above. Moreover, that subgraph has no odd cycle, is planar, and preserves cubicity. Does that work?
Anthony Labarre
CC BY-SA 3.0
2011-05-10T08:16:14.270Z
Yes, it works..
5501
CC BY-SA 3.0
2013-12-05T18:27:01.963Z
@AnthonyLabarre Your comment should be an answer. This answer is not correct since the gadget is not cubic. Your gadget is cubic ($BW_3$).
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-05-03T07:50:38.837Z
2011-05-03T07:50:38.837Z
5501
<p>I don't know about a reference, but if your cubic graph is connected, then such a decomposition yields a Hamiltonian path: since the graph is connected, there is at least one edge connecting the two cycles, so obtaining a Hamiltonian path in that way is straightforward. </p>

<p>The other direction seems trickier however; since there are graphs for which you can easily find a Hamiltonian path but no decomposition with respect to your criteria (see e.g. $K_{ 3,3}$), you need additional conditions on your input graph.</p>

CC BY-SA 3.0
2011-04-27T10:40:27.230Z
2011-05-02T13:04:55.373Z
2011-05-02T13:04:55.373Z
Anthony Labarre
<p>I posted this on <a href="https://mathoverflow.net/questions/61531/complexity-of-finding-disjoint-2-factors-with-equal-cardinality-in-cubic-graphs">mathoverflow</a> but with no luck:</p>

<p>Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two vertex-disjoint $(|V|/2)$-cycles in cubic graphs.</p>

<p>I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding two vertex-disjoint $(|V|/2)$-cycles with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?</p>

<p>Providing references is highly appreciated. $NP$-completeness refers to the decision version of the problem.</p>

CC BY-SA 3.0
2011-05-02T13:22:09.447Z
Do you mean that you wish to find a single 2-factor such that the cycles of the 2-factor can be partitioned into two groups with the same number of vertices in each group?  A factor is a (vertex) spanning subgraph, so it's not possible to have two vertex-independent factors of the same graph.
bbejot
CC BY-SA 3.0
2011-05-02T14:09:43.290Z
My understanding is that Mohammad wants to find two vertex-disjoint $(|V|/2)$-cycles.
Anthony Labarre
CC BY-SA 3.0
2011-05-02T22:13:03.623Z
Then please update the question (and title)...
Jukka Suomela
CC BY-SA 3.0
2011-05-03T09:00:16.140Z
By the way, isn't this question related?: http://cstheory.stackexchange.com/questions/1610/complexity-of-the-hamiltonian-subcycle-problem
Anthony Labarre
CC BY-SA 3.0
2011-05-03T10:26:36.847Z
But for the hardness results there, the graph needs not be connected. If you do not insist that your graph is connected, then you can simply use two copies of your original graph. A 2-factor with 2 cycles will induce a Hamiltonian cycle in your original graph.
5501
<cc.complexity-theory><reference-request><graph-theory><np-hardness>
Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?
Mohammad Al-Turkistany
# Complexity of finding 2 vertex-disjoint $(|V|/2)$-cycles in cubic graphs?

(Asked by: username_0 on 2011-04-15)

I posted this on [mathoverflow](https://mathoverflow.net/questions/61531/complexity-of-finding-disjoint-2-factors-with-equal-cardinality-in-cubic-graphs) but with no luck:

Finding a connected 2-factor is $NP$-complete since it is equivalent to the Hamiltonian cycle problem. I'm interested in the complexity of finding two vertex-disjoint $(|V|/2)$-cycles in cubic graphs.

I suspect that it is $NP$-complete but I'm not able to find a reference. Also, What is the complexity of finding two vertex-disjoint $(|V|/2)$-cycles with equal cardinality in planar cubic bipartite graphs? Is it $NP$-complete?

Providing references is highly appreciated. $NP$-completeness refers to the decision version of the problem.

**Tags:** cc.complexity-theory, reference-request, graph-theory, np-hardness

> **Comments:**
> **username_1**: Do you mean that you wish to find a single 2-factor such that the cycles of the 2-factor can be partitioned into two groups with the same number of vertices in each group?  A factor is a (vertex) spanning subgraph, so it's not possible to have two vertex-independent factors of the same graph.  
> **username_2**: My understanding is that Mohammad wants to find two vertex-disjoint $(|V|/2)$-cycles.  
> **username_3**: Then please update the question (and title)...  
> **username_2**: By the way, isn't this question related?: http://cstheory.stackexchange.com/questions/1610/complexity-of-the-hamiltonian-subcycle-problem  
> **username_4**: But for the hardness results there, the graph needs not be connected. If you do not insist that your graph is connected, then you can simply use two copies of your original graph. A 2-factor with 2 cycles will induce a Hamiltonian cycle in your original graph.  

---

## 2 answers

### Answer by username_4 on 2011-05-03. Score: 7 | Accepted answer

I assume, as stated in the comments, that the problem is to find a 2-factor with two cycles of length $|V|/2$ each in a cubic graph.
This problem is NP-complete:

1) HC in cubic graphs is NP-complete.

2) The following problem HC' is also NP-complete: Given a cubic graph $G$ and an edge $e$
in $G$, is there a Hamiltonian cycle through $e$. We can reduce HC to it: Given a graph $G$, replace one arbitrary vertex (left hand side) by a triangle with another vertex in it (right hand side):

![enter image description here](https://i.sstatic.net/bacge.jpg)

Call this new graph $G'$.
$G'$ is Hamiltonian iff $G$ is. Furthermore, if $G'$ is Hamiltonian, then for any red edge, there is a Hamiltonian cycle that contains this red edge. (Without the vertex in the middle, every Hamiltonian cycle contains two green edges and any green edge can then be replaced by two red ones.) The reduction from HC to HC' maps a cubic graph $G$ to $G'$ together with any red ege.

3) Finally, we reduce HC' to the problem of the question. Given an instance
$(G,e)$, we create two copies of $G$, subdivide $e$ in each copy and connected the two vertices that subdivide the two copies by a new edge $f$. This edge $f$ is a bridge in the new graph. If $G$ has a Hamiltonian cycle through $e$, then the new graph has a 2-factor consisting of two cycles of the same size.
Conversely, if the new graph has such a 2-factor, then it cannot use $f$. Therefore, it splits into two Hamiltonian cycles of the two copies. Since in these copies, the vertex subdividing $e$ has degree two, we get a Hamiltonian cycle of $G$ that contains $e$.

> **Comments:**
> **username_2**: Nice reduction. And it also answers the question under planarity and bipartiteness assumptions, since HC remains hard in that setting.  
> **username_4**: Planarity yes, but bipartiteness no, the reduction creates a triangle.  
> **username_2**: Oops, sorry, you are right.  
> **username_0**: @username_4, Thanks, really nice. However, I'll wait for the cubic planar bipartite case.  
> **username_2**: @username_0: Suggestion (haven't checked): replace a vertex with [$BW_3$](http://www.graphclasses.org/images/g_BW3.gif) instead of the above construction; the three vertices of degree 2 in that subgraph will play the role of the vertices of the triangle above. Moreover, that subgraph has no odd cycle, is planar, and preserves cubicity. Does that work?  
> **username_4**: Yes, it works..  
> **username_0**: @AnthonyLabarre Your comment should be an answer. This answer is not correct since the gadget is not cubic. Your gadget is cubic ($BW_3$).  

---

### Answer by username_2 on 2011-04-27. Score: 4

I don't know about a reference, but if your cubic graph is connected, then such a decomposition yields a Hamiltonian path: since the graph is connected, there is at least one edge connecting the two cycles, so obtaining a Hamiltonian path in that way is straightforward.

The other direction seems trickier however; since there are graphs for which you can easily find a Hamiltonian path but no decomposition with respect to your criteria (see e.g. $K\_{ 3,3}$), you need additional conditions on your input graph.


---

