Reducing one variant of Hamiltonian path to another

Question

Define

$A = \{<G,s,t> :G$ is un directed graph that has a Hamilton path from $s$ to $t\}$

$B = \{<G> :G$ is un directed graph that has a Hamilton path$\}$

I would like to show that $A \le_p B$.

My attempt:

Given $<G,s,t>$ , the reduction outputs $<G'>$ where $G'$ defines as follows:

we take $v_s$ and $v_t$ s.t there is an edge $e_s$ between $s$ and$v_s$ and an edge $e_t$ between $v_t$ and $t$.

Now we define $G' = (V',E')$ where $V' = V \cup \{v_0 , v_1\}$ and $E' = (E-\{e' :e' \ne e_s , s\in e'\} -\{e' :e' \ne e_t , t\in e'\}) \cup \{ \{v_0,v \} :\{v,s\} \in E \} \cup \{ \{v_1,v \} :\{v,t\} \in E \} \cup \{ \{v_0,s \}\ , \{v_1,t\} \}$.

Now, if $<G,s,t> \in A$ , let $s , u_1,\dots ,u_n ,t$ be the Hamilton path , then $s , v_0 , u_1 , \dots , u_n, v_1 ,t$ is a Hamilton path in $G'$.

The other direction does not work for me , if $G'$ has a Hamilton path then I want to say that the "end points" must be around $s,t$ but i'm not sure how to do that.

Answer 1

The simplest reduction, which is similar to what you were trying but simpler, is to add two new vertices to the graph in the instance of A: a vertex $v_s$ connected to $s$, and a vertex $v_t$ connected to $t$. Any Hamiltonian path in the new graph will connect $v_s$ to $v_t$, and so will restrict to a Hamiltonian path connecting $s$ to $t$. Vice versa, any Hamiltonian path in the original graph connecting $s$ to $t$ extends to a Hamiltonian path in the new graph connecting $v_s$ to $v_t$.