24
$\begingroup$

It is known that it is NP-complete to test whether a Hamiltonian cycle exists in a 3-regular graph, even if it is planar (Garey, Johnson, and Tarjan, SIAM J. Comput. 1976) or bipartite (Akiyama, Nishizeki, and Saito, J. Inform. Proc. 1980) or to test whether a Hamiltonian cycle exists in a 4-regular graph, even when it is the graph formed by an arrangement of Jordan curves (Iwamoto and Toussaint, IPL 1994).

For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?

The particular case I am interested in is 6-regular graphs, with the additional condition that the graph have an odd number of vertices. If this case could be shown to be NP-complete (or polynomial) it would have impact in a graph drawing problem described in http://arxiv.org/abs/1009.0579 . The "odd number of vertices" condition is because what I really want to know is, for 6-regular graphs, whether the graph contains either a Hamiltonian cycle or a bipartite 2-factor; but having an odd number of vertices eliminates the possibility of a bipartite 2-factor leaving only the possibility of a Hamiltonian cycle.

$\endgroup$
15
$\begingroup$

First step let assume the graph has even number of vertices. In the second stage, we will extend the construction, so that if k is even, then we will show how to turn the graph into having odd number of vertices.

The solution is a refinement of the idea suggested in the other answer.

First part

Claim: Given a $k$-regular graph $G$ with even number of vertices, one can compute a graph $H$ which is $(k+1)$-regular, and $H$ is Hamiltonian iff $G$ is Hamiltonian.

Proof: Take two copies of the $k$-regular graph $G$, let call them $G_1$ and $G_2$. For a vertex $v \in V(G)$, let $v_1$ and $v_2$ be the corresponding copies. Create a clique with $k+2$ vertices for $v$. Pick two vertices $v'$ and $v''$ in this clique, and remove the edge between them. Next, connect $v_1$ to $v'$ and $v_2$ to $v''$. Let $C(v)$ denote this component for $v$.

Repeat this for all the vertices of $G$, and let $H$ denote the resulting graph.

Clearly, the graph $H$ is $k+1$ regular. We claim that $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

One direction is clear. Given a Hambiltonian cycle in $G$, we can translate it into a cycle in $H$. Indeed, whenever the cycle visits a vertex $v$, we interpret it as moving from $v_1$ to $v_2$ (or vice versa) while visiting all the vertices in $C(v)$. As such, this results in a Hamiltonian cycle in $H$. (Note, that this is where we are using the fact that the original number of vertices is even - if the cycle is odd this breaks down.)

As for the other direction, consider a Hamiltonian cycle in $H$. It must be that $C(v)$ is visited by a portion of the cycle that starts in $v_1$, visits all the vertices of $C(v)$ and leaves from $v_2$ (or the symmetric option). Indeed, the Hamiltonian cycle can not enter and leave from the same $v_i$. As such, a Hamiltonian cycle in $H$ as a natural interpretation as a Hamiltonian cycle in $G$. QED.

Second part

As noted below by Tsuyoshi any 3-regular graph has even number of vertices. As such, the problem is hard for a $3$-regular graph with even number of vertices. Namely, the above reduction shows the problem is hard for any $k$-regular graph, although the resulting graph has an even number of vertices.

We observe, that this implies that the following problem is NP-hard.

Problem A: Deciding if a k-regular graph $G$ with even number of vertices has an Hamiltonian cycle going through a specific edge $e$.

However, if $k$ is even then given an instance $(G, e)$ we can reduce it to desired problem. Indeed, we replace the edge $e$ by a clique of $k+1$ vertices, as before deleting one edge in the clique, and connecting its two endpoints to the endpoints of $e$, and removing $e$ from the graph. Clearly, for the new graph $H$:

  • $H$ is $k$-regular.
  • $H$ is Hamiltonian iff $G$ is Hamiltonian with a cycle using $e$.
  • $H$ has $|V(G)| + k+1$ vertices => $H$ has odd number of vertices.

Note, that a $k$-regular graph, for $k$ odd, must have an even number of vertices (just count the edges), As such, there are no $k$-regular graphs with odd number of vertices, with $k$ being odd.


Result

It is NP-Hard to decide if a $k$-regular graph has a Hamiltonian cycle for $k\geq 3$. The problem remains NP-Hard even if the graph has an odd number of vertices.


Of course, it is always possible I made some stupid mistake...


Exercise

If we want to go from a graph that is $k$-regular to a graph that is (say) $2k$-regular then the graph resulting from applying the above reduction repeatedly results in a graph with a size that depends exponentially on $k$. Show, that given a $k$-regular graph $G$, and $i >2$, one can construct a graph $H$ that is $(k+i)$-regular and its size is polynomial in $k,i$ and $n$, where $n$ is the number of vertices of $G$. Furthermore, $G$ is Hamiltonian if and only if $H$ is Hamiltonian.

(I am posting this as an exercise, not a question, since I know how to solve this.)

$\endgroup$
  • 1
    $\begingroup$ Great! I think that this answer in fact settles the first question “For which other k is it known to be NP-complete to test Hamiltonicity of k-regular graphs?” because the 3-regular graphs have an even number of vertices, and the graph H made by this transformation also has an even number of vertices if G has an even number of vertices. $\endgroup$ – Tsuyoshi Ito Sep 25 '10 at 1:57
  • $\begingroup$ But unless I'm mistaken, the same counter-example to Robin's proof is a counter-example to this proof. Let G be the path on 2 vertices. Then the procedure here creates H, which is a 9 cycle, which is Hamiltonian. $\endgroup$ – Emil Sep 25 '10 at 10:37
  • $\begingroup$ As I said in regard to Robin's answer, the problem is that when you try to "project" the Hamilton cycle from H on to G, the cycle may end up not being a cycle, because it retraces where it has been. $\endgroup$ – Emil Sep 25 '10 at 10:40
  • $\begingroup$ @Emil: I think that the path on 2 vertices is really a special case because it has a Hamiltonian circuit if we are allowed to use the same edge more than once. $\endgroup$ – Tsuyoshi Ito Sep 25 '10 at 11:52
  • 1
    $\begingroup$ @Sariel Har-Peled: In every graph, the number of odd vertices (i.e. vertices of odd degree) is even. Therefore, all the 3-regular graphs have an even number of vertices. I had written an unnecessarily complicated argument without realizing this in the first version of comment (which I modified in less than 5 minutes), so excuse me if you read my old comment and were confused by it. $\endgroup$ – Tsuyoshi Ito Sep 25 '10 at 11:56
1
$\begingroup$

EDIT: This proof is wrong, as pointed out in the comments. (Should I delete the post?)

It intuitively feels like if Hamiltonicity is NP-hard for k-regular graphs, then it should also be NP-hard for (k+1)-regular graphs. Here's a back-of-the-envelope reduction, which looks fine to me, but of course there could be a mistake.

Let G be a k-regular graph. Let G' be a the graph Cartesian product of G and an edge. In other words, G' is the graph which has two copies of G, and every vertex is connected to its copy. G' is now (k+1) regular, since each vertex got 1 extra edge.

Claim: G has a Hamiltonian cycle if and only if G' has a Hamiltonian cycle.

Proof: If G has a Hamiltonian cycle, it's easy to see that G' has one too. Say (u,v) is an edge in the Hamiltonian cycle. Traverse the cycle from u to v without using that edge, and now instead of using the edge, go to v' from v, where v' is the vertex corresponding to v in the copy of G. Now traverse the cycle in the reverse order in this graph, which will bring us back to u'. Now go from u' to u, which completes the cycle.

If G' has a Hamiltonian cycle starting from vertex u, consider the same sequence of traversals on G. Every time a move is made to an adjacent vertex in the same graph, we make the same move in G. Every time a move is made to the corresponding vertex in the other graph, we do nothing. Since every move is valid on the graph G, and the cycle ends on vertex u, this is a Hamiltonian cycle.

$\endgroup$
  • 1
    $\begingroup$ I cannot see how the second paragraph of the proof works. If we drop the condition that G is k-regular, letting G be a path gives a counterexample to a claim that if G′ is Hamiltonian then G is also Hamiltonian. $\endgroup$ – Tsuyoshi Ito Sep 24 '10 at 23:10
  • 1
    $\begingroup$ I'm a bit concerned about the last paragraph here. When the Hamilton cycle for G' is "projected" (if that is the right word!) on to G, we may have a situation where the cycle retraces its steps. $\endgroup$ – Emil Sep 24 '10 at 23:11
  • $\begingroup$ @Tsuyoshi: you have got a counter-example: just take a regular path - the path with two vertices. $\endgroup$ – Emil Sep 24 '10 at 23:24
  • $\begingroup$ @Tsuyoshi: You're right. The proof is wrong. Should I delete the answer? Do we have a policy on this? $\endgroup$ – Robin Kothari Sep 24 '10 at 23:27
  • $\begingroup$ @Robin, I think your post should be left now that it has generated some discussion. It certainly illustrates that this is an awkward problem. $\endgroup$ – Emil Sep 24 '10 at 23:52

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.