8
$\begingroup$

I posted this on mathoverflow 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.

Improve this question
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – bbejot
    May 2, 2011 at 13:22
  • 2
    $\begingroup$ My understanding is that Mohammad wants to find two vertex-disjoint $(|V|/2)$-cycles. $\endgroup$
    – Anthony Labarre
    May 2, 2011 at 14:09
  • 1
    $\begingroup$ Then please update the question (and title)... $\endgroup$
    – Jukka Suomela
    May 2, 2011 at 22:13
  • 1
    $\begingroup$ By the way, isn't this question related?: cstheory.stackexchange.com/questions/1610/… $\endgroup$
    – Anthony Labarre
    May 3, 2011 at 9:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – 5501
    May 3, 2011 at 10:26

2 Answers 2

Reset to default
7
$\begingroup$

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

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

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ Nice reduction. And it also answers the question under planarity and bipartiteness assumptions, since HC remains hard in that setting. $\endgroup$
    – Anthony Labarre
    May 4, 2011 at 11:44
  • 1
    $\begingroup$ Planarity yes, but bipartiteness no, the reduction creates a triangle. $\endgroup$
    – 5501
    May 4, 2011 at 13:49
  • $\begingroup$ Oops, sorry, you are right. $\endgroup$
    – Anthony Labarre
    May 4, 2011 at 13:57
  • $\begingroup$ @5501, Thanks, really nice. However, I'll wait for the cubic planar bipartite case. $\endgroup$
    – Mohammad Al-Turkistany
    May 5, 2011 at 16:21
  • 1
    $\begingroup$ @Mohammad Al-Turkistany: Suggestion (haven't checked): replace a vertex with $BW_3$ 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? $\endgroup$
    – Anthony Labarre
    May 9, 2011 at 12:00
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

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

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