# Polynomial time reduction Hamiltonian path to TSP

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

• This is not particularly well-suited to math.stackexchange.com since cstheory.stackexchange.com already exists. – parsiad Jul 3 '16 at 16:16
• There are other polynomial reductions shown here, so I thought it would be the right thing to ask for help here – Tobias Jul 3 '16 at 16:28
• Please dont' use unnecessary abbreviations such as HAMPATH that are completely uncommon. – Jean Marie Jul 3 '16 at 16:31

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$.
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$.