Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

Question

The following is an excerpt from a material on NP-Theory:

"Let G be an undirected graph and let s and t be vertices in G. A Hamiltonian path in G is a
path from s to t using edges of G, on which each vertex of G appears once and only once. By
HAM-PATH we denote the problem of determining, given G, s and t, whether G contains a
Hamiltonian path from s to t. I now explain a reduction
HAM-PATH < HAM-CYCLE.
Let G, s, t constitute an input for HAM-PATH. We want to convert it to an input G′ (an
undirected graph) for HAM-CYCLE. We add a new vertex u to the vertex set of G in order
to obtain the vertex set for G′. The edges of G′ are all the edges of G plus two extra edges
(u, s) and (t, u). I leave it to the reader to visualize that G′ contains a Hamiltonian cycle if
and only if G contains a Hamiltonian path from s to t."
I am confused as to why do we need to add a vertex u to create G′. Why can't we simply connect s and t and then check for a Hamiltonian Cycle. If it exists, then a path would also exist(as path is a sub-graph of cycle in an undirected graph) and we would be done. What am I missing? I am specially asking this for undirected graphs. I am clear about directed graphs that existence of cycle having s and t does not guarantee Hamiltonian path.

Illustrations or counter examples are welcome!

Richie Yeung · Answer

If the vertex $u$ is not added to to $G'$, then a Hamiltonian cycle in $G'$ does not necessarily correspond to a Hamiltonian path from $s$ to $t$. This is because the cycle may not have $s, t$ adjacent to each other.
For example, one could have

Since there is no Hamiltonian path from $s$ to $t$ in the first graph, there is no Hamiltonian cycle in the second graph. However, if you didn't include $u$,

then there is a Hamiltonian cycle so the reduction fails.

Pseudonym · Answer

Hint: Suppose that $G$ already had a Hamiltonian cycle, but no Hamiltonian path from $s$ to $t$.
OK, this clearly needs more explanation.
Consider the case of an undirected cycle graph with 4 vertices.

This graph, $G$, has a Hamiltonian cycle, but it does not have a Hamiltonian path from $0$ to $2$.
Now add an edge $(2,0)$, to obtain a new graph, $G'$. This graph obviously has a Hamiltonian cycle, because it has the same one that $G$ has. So just because $G'$ has a Hamiltonian cycle, that doesn't mean that $G$ had the specific Hamiltonian path that you were looking for.

Confusion in Reduction of Hamiltonian-Path to Hamiltonian-Cycle

2 Answers

Add your own answers!

Ask a Question