Polynomial time reduction Hamiltonian path to TSP

Question

is there a polynomial time reduction from Hamiltonian Path to TSP? If so, could you tell me?

Thank you in advance! Toby

Answer 1

An instance of Hamiltonian cycle is a graph $G=(V,E)$ with finite vertex set $V=\{1,\ldots,n\}$. Let $G^\prime=(V,W)$ be a complete weighted digraph with the same vertex set and weight matrix $W=(w_{ij})$ ($w_{ij}$ gives the weight of the edge from $i$ to $j$) given by $$ w_{ij}=\begin{cases} 1 & \text{if }(i,j)\in E;\\ 2 & \text{if }(i,j)\notin E. \end{cases} $$ There is a Hamiltonian cycle in $G$ if and only if there is a cycle of length at most $n$ in $G^\prime$.

For the last part of the argument, you also need this.

---

Addendum (direct reduction): An instance of Hamiltonian path is a graph $G=(V,E)$ with vertex set $V=\{1,\ldots,n\}$. Let $G^\prime=(V\cup\{0\},W)$ be a complete weighted digraph with weight matrix $W$ given by $$ w_{ij}=\begin{cases} 0 & \text{if }i=0\text{ or }j=0;\\ 1 & \text{if }(i,j)\in E;\\ 2 & \text{if }(i,j)\notin E. \end{cases} $$ There is a Hamiltonian path in $G$ if and only if there is a cycle of length at most $n-1$ in $G^\prime$.