16
$\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
    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

24

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
    @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
17

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.

  • 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