patternMinor
HamCycle to HamPath reduction
Viewed 0 times
hampathreductionhamcycle
Problem
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?
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?
Solution
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:
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:
Context
StackExchange Computer Science Q#9669, answer score: 4
Revisions (0)
No revisions yet.