I have to show that HP polynomially transforms HC by following steps:
$(1)$ Construct a polynomial transformation $f$ from HP to HC.
$(2)$ Show for all graphs $G$ that $G ∈ YHP ⇒ f(G) ∈ YHC$.
$(3)$ Show for all graphs $G$ that $f(G) ∈ YHC ⇒ G ∈ YHP$.
Can you give some guidelines? Thanks!
Given $G,s,t$ to find a hampath inside connect $s,t$ with a new midway vertex, $r$ and add the edges $(t,r)$ and $(r,s)$. Prove the correctness.
If the version of the problem that you work with is only a graph $G$: you can connect each vertex in $G$ with $r$ both ways, i.e. add the edges $(v,r)$ and $(r,v)$ for every $v\in V$.
$f(G)$ is the new graph.
The reduction is in linear time of course.
If there is a HP from $u$ to $v$ in $G$, lets say $p$ then $p\ \cup \{(v,r), (r,u)\}$ is a HC in the output graph.
If there is a HC in $f(G)$ then there is exactly one edge in the cycle that goes in to $r$, say $(v,r)$ and exactly one edge that goes out of $r$ in the cycle, say $(r,u)$, it is easy to see that the cycle without those edges is a HP from $u$ to $v$ in $G$.