Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Abaco, my answer, which you accepted, is wrong. Aryabhata has given a correct solution. –  Mike Spivey Oct 24 '11 at 21:06
    
@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. –  Shushan Wen Oct 11 '13 at 20:56

3 Answers 3

up vote 10 down vote accepted

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

share|improve this answer
    
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) –  Lital Zubery Dec 19 '12 at 13:24
    
@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. –  Aryabhata Dec 19 '12 at 17:20

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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