0
$\begingroup$

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 node t' to 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?

$\endgroup$
  • $\begingroup$ Have you tried writing a proof of what you propose (i.e., that the same reduction works in the undirected case)? $\endgroup$ – dkaeae Aug 13 '19 at 8:46
  • $\begingroup$ I meant the same reduction of $UHAMPATH \leq_p UHAMCYCLE$ would work in both explanation + reduction. $\endgroup$ – tim timothy Aug 13 '19 at 8:50
  • $\begingroup$ Perhaps you should add a link to this other reduction. I see nothing wrong with your proof (see also xskxzr's answer). $\endgroup$ – dkaeae Aug 13 '19 at 8:55
0
$\begingroup$

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.

$\endgroup$

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.