Metric TSP

Overview

The Travelling Salesman Problem (TSP) is a classic problem where you have a set of cities and distances between each pair of them. The goal is to find the shortest possible route that visits each city once and returns to the origin city. As simple as it might sound at first, this problem becomes quite intractable: the optimization version of TSP is NP-hard.

But there’s a variant of this problem called the "metric" TSP. In this version, the distances between cities satisfy the “triangle inequality”, meaning the direct route from one city to another is never longer than the route going through a third city. This is handy because this happens to be how Euclidean distance works and as such, how distances are measured in the real world. So this version of the problem lets us use a handy approximation algorithm that is guaranteed to be within a constant factor of the optimal solution!

An Observation

Consider a complete weighted graph representing our cities and the distances between them. Suppose we find a minimum spanning tree (MST) of this graph. The MST connects every vertex while minimizing the total weight of its edges.

Let $OPT$ be the cost of an optimal TSP tour and let $MST$ be the cost of a minimum spanning tree. If we remove one edge from an optimal TSP tour, what remains is a spanning tree. Since the MST is the minimum-cost spanning tree,

$$MST\leq OPT.$$

This gives us a useful lower bound on the optimal TSP solution. If we can construct a tour whose cost is at most twice the cost of the MST, we will automatically have a tour whose cost is at most twice the optimum.

The Algorithm

Now, consider an algorithm for metric TSP: find a minimum spanning tree in the graph, then define a walk that starts at the root of the tree and follows the tree in the order produced by a Depth-First Search (DFS).

Because every edge of a tree is traversed once going down and once coming back up, the total length of this walk is exactly twice the cost of the minimum spanning tree:

$$cost(W)=2\cdot MST.$$

The problem is that this walk may visit the same city several times. But because the graph satisfies the triangle inequality, we can skip cities that we have already visited and go directly to the next unvisited city without increasing the total cost of the tour.

This shortcutting step gives us a valid TSP tour while preserving the upper bound:

$$cost(TSP)\leq 2\cdot MST.$$

The Approximation Guarantee

We already know that

$$MST\leq OPT.$$

Combining this with the cost of the tour produced by the algorithm gives

$$cost(TSP)\leq 2\cdot MST\leq 2\cdot OPT.$$

Therefore, the algorithm is a $2$-approximation algorithm: the tour it produces is guaranteed to have cost no more than twice the cost of the optimal tour.

Why Does the Triangle Inequality Matter?

The shortcutting step is where the metric assumption becomes essential. Suppose our DFS walk visits cities $A$, $B$, and $C$ in that order, but $B$ has already been visited. We can replace the detour through $B$ with a direct edge from $A$ to $C$.

The triangle inequality guarantees that

$$d(A,C)\leq d(A,B)+d(B,C).$$

Thus, shortcutting repeated vertices cannot make the tour longer. Without the triangle inequality, this argument breaks down, and the same approximation guarantee is no longer available.

A Broader Connection

Metric TSP is a useful example of how a difficult optimization problem can become tractable when we are willing to accept an approximate solution. The minimum spanning tree does not itself solve TSP, but it gives us a structure whose cost is guaranteed to be no greater than the optimal tour.

The triangle inequality then lets us turn that structure into a valid tour without losing our bound. The result is a simple algorithm with a rigorous guarantee: even though we cannot efficiently find the exact optimum in general, we can efficiently find a solution that is never more than twice as expensive.