[Solved]: HamCycle to HamPath reduction

Problem Detail: 

I've seen a reduction that's done by adding another vertex to the graph and creating a path through that vertex.

Why do I need to add a vertex? Cant I just remove an edge? Lets say the graph with the HamCycle is G,s,t when removing the edge between s and t dont I get a path the goes through all the vertexes that's qualified as a Hamiltonian path?

Asked By : user6821

Answered By : Vor

First of all I think that the direction of the reduction of your question is from Hampath to Hamcycle (you prove the NP-hardness of Hamcycle reducing the NP-complete problem Hampath to it).

Now given an instance of Hampath: $G,s,t$:

1) there is an edge between $s$ and $t$
2) there is not an edge between $s$ and $t$

In both cases the extra node $u$ is needed in order to force $s,u,t$ to be consecutive nodes in the Hamiltonian cycle.

The new graph $G'$ with a new node $u$ and new edges $(s,u), (u,t)$ (in the first case you split the original edge) will have an Hamiltonian cycle iif the original graph $G$ has an Hamiltonian path from $s$ to $t$.

You can "play" with these two graphs:

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9669