0
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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

enter image description here

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

enter image description here

then there is a Hamiltonian cycle so the reduction fails.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for those clear illustrations!! $\endgroup$ – Puneet Jul 20 at 4:58
1
$\begingroup$

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.

Example graph

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ How is that possible? If I have a Hamiltonian cycle, I will remove the edge between s to t. And I get a Hamiltonian path. Did I miss something? $\endgroup$ – Puneet Jul 18 at 8:57
  • $\begingroup$ Suppose $G$ is a (directed) cycle graph with 100 vertices. It only has 100 Hamiltonian paths in it. You could add any additional edge to form $G'$, and that graph would have a Hamiltonian cycle. That doesn't mean $G$ had a Hamiltonian path corresponding to that specific added edge. $\endgroup$ – Pseudonym Jul 18 at 9:45
  • $\begingroup$ I am confused about the undirected case! $\endgroup$ – Puneet Jul 18 at 14:34
  • $\begingroup$ Got it! Thanks I was not able to visualize this counter example. $\endgroup$ – Puneet Jul 20 at 4:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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