Hamilton path reduction to Hamilton cycle

522 Views Asked by At

HAMILTON PATH: given a directed graph $G$ and $2$ nodes start and end does there exist a hamilton path from start to end?

HAMILTON CYCLE: given a directed graph $G$ and $1$ node start, does there exist a hamilton cycle thats starting at start?

Can hamilton path be reducable to hamilton cycle ?

my reduction is adding another node end' and letting it have an edge from end to end', and, end' to start.

Confusing on showing $(G, start, end) \in HAMILTON PATH \Leftrightarrow (G, start) \in HAMILTON CYCLE$

The first part is easy

if $(G, start, end) \in HAMILTON PATH$, then there is a path for random vertex r $\{(s,r_1), (r_1, r_2), ..., (r_n, end) \}$ and by hamilton path algorithm $\{(s,r_1), (r_1, r_2), ..., (r_n, end), (end, end'), (end', s) \}$. By definition $(G, start) \in HAMILTON CYCLE$

Now the 2nd part

$(G, start, end) \notin HAMILTON PATH$, ... , then $(G, start, end) \notin HAMILTON CYCLE$

I'm not sure how to explain the second part.. Not really sure if its possible right now

1

There are 1 best solutions below

2
On BEST ANSWER

I think you should start with a cycle in $$G' = (V \cup \{end'\}, E \cup \{\{end', end\}, \{end' ,s\}\}).$$ Then cycle is w.l.o.g. $((end', s), (s, r_1), (r_1, r_2), \ldots, (r_n, end), (end, end'))$ (in your definitions).

Remove those two edges $\{end', s\}$ and $\{end, end'\}$ and you end up with a path from $s$ to $end$ in the $G'$, and also in the original graph $G$.