# Guidelines to reduce general TSP to Triangle TSP

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.

• 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|. – Marzio De Biasi Oct 10 '12 at 11:26
• Homework perhaps? – Kristoffer Arnsfelt Hansen Oct 10 '12 at 13:20
• @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. – Yoshio Okamoto Oct 11 '12 at 1:20
• @YoshioOkamoto: There is in fact an easy reduction, and I would classify it as an exercise. – Kristoffer Arnsfelt Hansen Oct 11 '12 at 9:22
• @KristofferArnsfeltHansen: That's interesting. I'd love to see. – Yoshio Okamoto Oct 12 '12 at 11:53

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.

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