0
$\begingroup$

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

Thank you in advance! Toby

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

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

$\endgroup$
  • $\begingroup$ Thanks for your answer! So, there is no direct reduction from hamiltonian path to tsp? Instead, you have to reduce hamiltonian path to hamiltonian cycle first, then reduce hamiltonian cycle to travelling salesman problem, right? $\endgroup$ – Tobias Jul 3 '16 at 17:09
  • $\begingroup$ No, it's a simple modification of the above. I have added it. $\endgroup$ – parsiad Jul 3 '16 at 17:49

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.