<p>Here is a simple reduction for the TSP problem to the metric TSP problem:</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-10-22T15:14:32.760Z
easy ... but only when you know how to do it :-) +1!
Marzio De Biasi
CC BY-SA 3.0
2017-02-03T16:05:16.563Z
Can you tell why this reduction is not an _approximation-preserving reduction_?
Ribz
CC BY-SA 4.0
2019-03-18T23:57:56.897Z
This answer is discussed in this comment on Hacker News, which explains why the approximation is not preserved. https://news.ycombinator.com/item?id=11582704
Steven Waterman
CC BY-SA 3.0
2012-10-22T15:02:38.343Z
2012-10-23T18:24:13.263Z
2012-10-23T18:24:13.263Z
Kristoffer Arnsfelt Hansen
<p>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:</p>

<p>$D(a, b) \leq D(a, c) + D(c, b)$</p>

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

CC BY-SA 3.0
2012-10-10T11:26:36.857Z
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
CC BY-SA 3.0
2012-10-10T13:20:07.210Z
Homework perhaps?
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-10-11T01:20:41.090Z
@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
CC BY-SA 3.0
2012-10-11T09:22:21.743Z
@YoshioOkamoto: There is in fact an easy reduction, and I would classify it as an exercise.
Kristoffer Arnsfelt Hansen
CC BY-SA 3.0
2012-10-12T11:53:47.383Z
@KristofferArnsfeltHansen: That's interesting. I'd love to see.
Yoshio Okamoto
CC BY-SA 3.0
2012-10-22T10:24:23.213Z
@KristofferArnsfeltHansen: I didn't think of it too much, but I don't see a quick reduction, too. Can you post it as an answer?
Marzio De Biasi
<cc.complexity-theory><np-hardness><np><tsp><hamiltonian-paths>
Guidelines to reduce general TSP to Triangle TSP
Dave
# Guidelines to reduce general TSP to Triangle TSP

(Asked by: username_0 on 2012-10-10)

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.

**Tags:** cc.complexity-theory, np-hardness, np, tsp, hamiltonian-paths
> **Comments:**
> **username_1**: 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|.  
> **username_2**: Homework perhaps?  
> **username_3**: @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.  
> **username_2**: @YoshioOkamoto: There is in fact an easy reduction, and I would classify it as an exercise.  
> **username_3**: @KristofferArnsfeltHansen: That's interesting. I'd love to see.  
> **username_1**: @KristofferArnsfeltHansen: I didn't think of it too much, but I don't see a quick reduction, too. Can you post it as an answer?  

---

## 1 answers

### Answer by username_2 on 2012-10-22. Score: 21

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.

> **Comments:**
> **username_1**: easy ... but only when you know how to do it :-) +1!  
> **username_4**: Can you tell why this reduction is not an _approximation-preserving reduction_?  
> **username_5**: This answer is discussed in this comment on Hacker News, which explains why the approximation is not preserved. https://news.ycombinator.com/item?id=11582704  

---

