# Is the reduction for HAMPATH to HAMCYCLE and UHAMPATH to UHAMCYCLE the same?

HAMPATH/UHAMPATH is A directed / undirected graph G and 2 nodes s and t and is there a hamilton path from s to t?

Likewise with HAMCYCLE/UHAMCYCLE but has a hamilton cycle on $$G'$$

The reduction for directed is

$$HAMPATH \leq_p HAMCYCLE$$

function(G, s, t)
G' = G
add edges (t, t') and (t', s)
return (G')


$$(\Rightarrow)$$If $$(G, s, t) \in HAMPATH$$, then $$\{(s, v_1), \dots, (v_n, t)\}$$ is a hamilton path in $$G$$ from $$s$$ to $$t$$ and our reduction for $$G'$$ has a path $$\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$$ which is a hamilton cycle $$(G') \in HAMCYCLE$$

$$(\Leftarrow)$$ If $$(G') \in HAMCYCLE$$, then $$\{(s, v_1), \dots, (v_n, t), (t, t'), (t', s)\}$$ is a hamilton cycle in $$G$$. Remove the edges $$(t, t')$$ and $$(t', s)$$ and we are left with a hamilton path $$\{(s, v_1), \dots, (v_n, t)\}$$, $$(G, s, t) \in HAMPATH$$

Wouldn't this reduction also work for the undirected version i.e. $$UHAMPATH \leq_p UHAMCYCLE$$? I've seen on the internet another reduction where they add another node and add an edge between every vertex in G for $$G'$$ but wouldn't this simpler version work as well?

• Have you tried writing a proof of what you propose (i.e., that the same reduction works in the undirected case)? Aug 13, 2019 at 8:46
• I meant the same reduction of $UHAMPATH \leq_p UHAMCYCLE$ would work in both explanation + reduction. Aug 13, 2019 at 8:50
Your reduction is correct. However, the standard Hamiltonian path problem does not specify the endnodes $$s$$ and $$t$$, which is a bit different from your definition. This is possibly why the internet does not use your simple reduction.