4 ms·

You’re right, it doesn’t. However, in TSP you are allowed to visit each vertex exactly once. So traversing the minimum spanning tree naively is not a valid so

You’re right, it doesn’t. However, in TSP you are allowed to visit each vertex *exactly* once. So traversing the minimum spanning tree naively is not a valid solution. What you the approximation does is to „shortcut“ the paths if you would revisit an already seen vertex again. That’s where you need the triangle inequality to guarantee that the shortcut isn’t longer than the path through the minimum spanning tree. Otherwise you cannot guarantee an approximation ratio of at most 2.

inigyou 2mo ago
So we see that a slight modification of the problem makes the approximation work for all graphs.
- LPisGood 2mo ago
  Elaborate on the proposed modification — are you referring to the fact that this can be done if distances obey a metric function?
  - inigyou 2mo ago
    If you modify the problem to allow passing by a node that you've already visited then the spanning tree approximation works for all graphs.