2 ms·

Does minimum spanning tree rely on the triangle inequality? I thought it worked on arbitrary graphs

• mockerell 3mo ago
  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 3mo ago
    So we see that a slight modification of the problem makes the approximation work for all graphs.
    • LPisGood 3mo ago
      Elaborate on the proposed modification — are you referring to the fact that this can be done if distances obey a metric function?
      • inigyou 3mo 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.