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.

Improve this question
$\endgroup$
6
  • $\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
    Commented Oct 10, 2012 at 11:26
  • 2
    $\begingroup$ Homework perhaps? $\endgroup$
    – Kristoffer Arnsfelt Hansen
    Commented Oct 10, 2012 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
    Commented Oct 11, 2012 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
    Commented Oct 11, 2012 at 9:22
  • 1
    $\begingroup$ @KristofferArnsfeltHansen: That's interesting. I'd love to see. $\endgroup$
    – Yoshio Okamoto
    Commented Oct 12, 2012 at 11:53

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ easy ... but only when you know how to do it :-) +1! $\endgroup$
    – Marzio De Biasi
    Commented Oct 22, 2012 at 15:14
  • 1
    $\begingroup$ Can you tell why this reduction is not an approximation-preserving reduction? $\endgroup$
    – Ribz
    Commented Feb 3, 2017 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 Waterman
    Commented Mar 18, 2019 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.