I'll define the problems
UHAMPATH
Input: A undirected graph G and 2 nodes, s and t
Question: Is there a hamiltonian path from s to t in G?
UHAMCYCLE
Input: A undirected graph G
Question: Is there a hamiltonian cycle in G?
$$UHAMCYCLE \leq_p UHAMPATH$$
my reduction is as followed $(G) \to (G', s, t)$
function(G)
for each e = (u, v) in E(G)
G' = G
add nodes u' and v' to G'
add edges (u', u) and (v, v')
s = u'
t = v'
if there is a hamilton path from s to t:
return (G', s, t)
Basically if there is a hamilton cycle in G then some edge in $G$ will form a hamilton path in $G'$.
An example to further illustrate the reduction:
Graph G
(a) ---- --(d)
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \| |
(b) ------ (c)
Has a clear Hamilton cycle (a, b, c, d).
If we choose edges (a, d)
Graph G'
(s)--(a) ---- --(d)
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \|
(b) ------ (c)--(t)
Doesn't have a hamilton path from s to t. However if you choose any other edge such as (a, d) then
(s)--(a) ---- --(d)--(t)
| \ |
| \ |
| \ |
| \ |
| \ |
| \ |
| \|
(b) ------ (c)
$(s \to a \to b \to c \to d \to t)$. Holds.
I'm confused whether or not I can use this line:
if there is a hamilton path from s to t:
return (G', s, t)
Checking to see if a graph has a hamilton path is NP complete but since we are looking to reduce it to it I think we can?