6
$\begingroup$

I am looking for the method / correct way to approach to reduce the traveling salesman problem to an instance of traveling salesman problem which satisfies the triangle inequality, ie:

$D(a, b) \leq D(a, c) + D(c, b)$

I am not sure how to attack this kind of problem, so any pointers / explanations regarding this would be helpful. Thank you.

$\endgroup$
  • $\begingroup$ You can use a direct reduction from Hamiltonian Cycle problem on planar graphs (NPC). Assign weight 1 if two nodes are connected, weight 2 if the two nodes are not connected; the planar graph has a Hamiltonian cycle iif there is a tour of cost <= |V|. $\endgroup$ – Marzio De Biasi Oct 10 '12 at 11:26
  • 2
    $\begingroup$ Homework perhaps? $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 10 '12 at 13:20
  • $\begingroup$ @MarzioDeBiasi: The question doesn't ask to prove the metric TSP is NP-hard, but asks for a reduction of the TSP to the metric TSP. I don't see an "easy" reduction right now. $\endgroup$ – Yoshio Okamoto Oct 11 '12 at 1:20
  • 2
    $\begingroup$ @YoshioOkamoto: There is in fact an easy reduction, and I would classify it as an exercise. $\endgroup$ – Kristoffer Arnsfelt Hansen Oct 11 '12 at 9:22
  • 1
    $\begingroup$ @KristofferArnsfeltHansen: That's interesting. I'd love to see. $\endgroup$ – Yoshio Okamoto Oct 12 '12 at 11:53
21
$\begingroup$

Here is a simple reduction for the TSP problem to the metric TSP problem:

For the given TSP instance with $n$ cities, let $D(i,j) \geq 0$ denote the distance between $i$ and $j$. Now let $M = \max_{i,j} D(i,j)$. Define the metric TSP instance by the distances $D'(i,j) := D(i,j)+M$. To see that this gives a metric TSP instance, let $i,j,k$ be arbitrary. Then $D'(i,j) + D'(j,k) = D(i,j) + D(j,k) + 2M \geq 2M \geq D(i,k) + M = D'(i,k)$. Since any tour uses exactly $n$ edges, the transformation adds exactly $nM$ to any tour, which shows the correctness of the reduction.

Remark: We can of course also allow for negative distances in the original TSP instance if you prefer by changing the reduction slightly.

$\endgroup$
  • 1
    $\begingroup$ easy ... but only when you know how to do it :-) +1! $\endgroup$ – Marzio De Biasi Oct 22 '12 at 15:14
  • 1
    $\begingroup$ Can you tell why this reduction is not an approximation-preserving reduction? $\endgroup$ – Ribz Feb 3 '17 at 16:05
  • $\begingroup$ This answer is discussed in this comment on Hacker News, which explains why the approximation is not preserved. news.ycombinator.com/item?id=11582704 $\endgroup$ – Steven Lowes Mar 18 at 23:57

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.