14
$\begingroup$

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone help me here? (linking a source is also good).

Thank you.

  • 0
    Abaco, my answer, which you accepted, is wrong. Aryabhata has given a correct solution.2011-10-24
  • 1
    @user96758: I think you're right. Given a vertex, among all the edges attached to it, at least 2 are in a HC (if it exists). In fact, when one of these 2 edges, say $e$ (without loss of generality, $e = \{u,v\}$, from $u$ to $v$), is removed, the new graph will have a HP starting from $v$ and ending at $u$. So we don't need additional vertices to reduce HC problem to HP problem. On the other hand, since the reducing cost is polynomial in all methods mentioned here and by other users, we just proved the same thing.2013-10-11
  • 0
    I found a much more compact solution in here: http://aduni.org/courses/algorithms/courseware/psets/Problem_Set_06_Solutions.html2016-07-28

5 Answers 5

23

Note: The below is a Cook reduction and not a Karp reduction. The modern definitions of NP-Completeness use the Karp reduction.

For a reduction from Hamiltonian Cycle to Path.

Given a graph $G$ of which we need to find Hamiltonian Cycle, for a single edge $e = \{u,v\}$ add new vertices $u'$ and $v'$ such that $u'$ is connected only to $u$ and $v'$ is connected only to $v$ to give a new graph $G_e$.

$G_e$ has a Hamiltonian path if and only if $G$ has a Hamiltonian cycle with the edge $e=\{u,v\}$.

Run the Hamiltonian path algorithm on each $G_e$ for each edge $e \in G$. If all graphs have no Hamiltonian path, then $G$ has no Hamiltonian cycle. If at least one $G_e$ has a Hamiltonian path, then $G$ has a Hamiltonian cycle which contains the edge $e$.

  • 0
    I think you wrong about the reduction from HC to HP (answer #1). If we look about this case : U* ------------ *V and implement your reduction: U'* -------- U* ------------ V* ----------V'* It is prettry easy to see that in the graph after redcution there is an hemilton path .. (u' -> u -> v -> v') Hope to here your response (maybe I didn't understand the reduction)2012-12-19
  • 0
    @LitalZubery: If I understood you correctly, you are talking about the special case where G is exactly one single edge? Yes, that should be mentioned, but does not really break down the proof, as a finite number of exceptions will not hurt the NP-Completeness proof.2012-12-19
  • 0
    I am confused, is this valid?2015-04-21
  • 0
    @graphtheory92: Seems valid to me. What are your concerns?2015-04-26
  • 0
    I am commenting on behalf of @RohitKumarJena (He cannot comment because he hasn't enough reputation) , He suggested an edit which said that something in this answer is wrong (I don't know about that) You can see what he said on the 4th version of this edit. I improved his edit and removed his part(because I don't know whether it is correct) so that his point remains there and I trivially edited to apply changes. Please do see that (He may be correct)2017-04-14
  • 0
    @JaideepKhare: Thanks for letting me know. Yes, the edit with the counterexample was wrong. The statement is "there is a hamiltonian path in $G_e$ iff there is a hamiltonian cycle in $G$ which _contains_ the edge $e$". The example given didn't have that property (hamiltonian cycle with that given edge). I have also rolled back to a previous version.2017-04-17
  • 0
    How do you know the Hamilton cycle go through that edge you chose? Maybe you should add a proper proof.2017-06-23
  • 0
    @kuhaku: We don't. That is why we loop through all the edges. Read the last paragraph.2017-06-27
  • 3
    What precisely is the many-one reduction being described here? In order to show that a problem is NP complete we must use polynomial time many-one reductions, not polynomial time Turing reductions.2018-03-24
  • 0
    @CarlMummert: This is using a Cook reduction of course. There has been no attempt made to use a Karp reduction.2018-03-26
  • 2
    @Aryabhata: indeed, but then it does not prove that anything is NP complete, as the question asked.2018-03-26
  • 0
    @CarlMummert: I guess things have changed since I learnt all this stuff. Let me see if I can add a Karp reduction.2018-03-26
11

This is a reduction from undirected Hamilton Cycle to undirected Hamilton Path. It takes a graph $G$ and returns a graph $f(G)$ such that $G$ has a Hamilton Cycle iff $f(G)$ has a Hamilton Path.

Given a graph $G = (V,E)$ we construct a graph $f(G)$ as follows.

Let $v \in V$ be a vertex of G, and let $v',s,t \notin V$.

We want to make $v'$ a "copy" of $v$, and add vertices of degree one; $s,t$, connected to $v,v'$, respectively. (See Figure 1.)

That is, $f(G)$ has vertices $V\cup \{v',s,t\}$ and edges $E\cup\{(v',w)|(v,w)\in E\}\cup\{(s,v),(v',t),(v,v')\}$.

Now if $G$ has a Hamilton Cycle, we may write it on the form $(v,u),edges,(u',v)$, where $edges$ is some list of edges which must form a simple path $u\ldots u'$ visiting all vertices but $v$. But then, $(s,v),(v,u),edges,(u',v'),(v',t)$ is a Hamilton Path between $s$ and $t$ in $f(G)$.

If on the other hand $f(G)$ has a Hamilton Path, then it must have $s$ and $t$ as endpoints, since they have degree 1. In which case it must (up to reversal) be of the form $(s,v),(v,y),edges',(y',v'),(v',t)$. But then, $G$ has a Hamilton cycle $(v,y),edges',(y',v)$.

Hamilton Cycle to Hamilton Path reduction

  • 3
    This should be the correct answer2018-02-25
3

For the directed case,

Given $\langle G=(V,E)\rangle$ for the Hamiltonian cycle, we can construct input $\langle G',s,t\rangle$: choose a vertex $u \in V$ and divide it into two vertices, such that the edges that go out of $u$, will go out of $s$ and the vertices that get in to $u$, will get in to $t$.

0

The answer mentioned is correct for the purpose of showing reduction, but I have this idea which is faster than the idea presented. Please correct me if I am wrong. If ham path says no for even a single vertex then ham cycle says no. This means that all vertices should now say yes for Ham path(hence one method id to ask each egde).A faster method would be: Pick any vertex. For each of its edge remove the edge and add 2 vertices and join in same fashion as mentioned in the answer. If for any edge removal and addition of 2 new vertices ham path says yes, then output Yes.

Please correct me if I am wrong.

  • 0
    How is this faster than the other ideas presented?2016-07-28
0

Just remove one edge from G, this will construct a G'. There's a Hamiltonian path in G' iff There's a Hamiltonian cycle in G.

  • 2
    This is untrue, at least in the brief version you gave. Let $G$ be the graph with five vertices and five edges that corresponds to the shape of capital letter **A**. Removing the horizontal crossing edge gives five vertices and four edges that we designate graph $G'$. While $G'$ has a Hamiltonian path (it is a path), the graph $G$ does not have a Hamiltonian cycle.2016-12-03
  • 0
    Oh, it is my mistake that I didn't write the full reduction. Thanking for pointing that hardmath. I must state that if there's a Hamiltonian path in G' from u to v where (u,v) is the edge removed. And if G is directed graph, we must also check whether the direction of the edge (u,v) and choose the proper starting point u or v for Hamiltonian path. By the way, I think my reduction by removing one edge is not proper since it must be vertex u and vertex v must be the starting and ending vertices (or vice versa). Therefore, we should add two more vertices instead of removing edge.2016-12-12
  • 0
    Thanks for responding. Please edit your Answer to reflect what you think will provide a valid reduction of one problem to the other, esp. from Hamiltonian cycle to Hamiltonian path as called for by the Question.2016-12-12