Approximating Metric TSP

The Traveling Salesman Problem asks for a Hamiltonian cycle of minimum total weight in a complete edge-weighted graph. Metric TSP is the restriction where edge weights $w$ satisfy the triangle inequality:

Equivalently, going directly from $u$ to $v$ is never more expensive than any detour through a third vertex. This holds automatically when weights are shortest-path distances in an underlying graph, or Euclidean/Manhattan distances in the plane, which makes the metric case enormously important in practice: routing, circuit board drilling, and clustering all inherit this structure. The key algorithmic move in both algorithms below is to relax the Hamiltonian-cycle requirement to a weaker structure that is easy to compute optimally, then repair it back into a valid tour. A spanning tree connects all vertices with $n-1$ edges and no cycles; an Eulerian circuit traverses every edge of a graph exactly once and exists if and only if every vertex has even degree (and the graph is connected). Neither object is itself a Hamiltonian cycle, but each can be massaged into one using the triangle inequality to justify "shortcutting" — skipping over already-visited vertices without increasing the total cost. The central inequality used repeatedly is $w(\text{MST}) \le \text{OPT}$: deleting any single edge from an optimal tour produces a spanning tree, so no spanning tree — in particular the minimum one — can cost more than the tour. This turns the minimum spanning tree into a computable, polynomial-time lower bound certificate against which we measure our constructed tour, exactly the strategy used in the Vertex Cover 2-Approximation, where a matching serves as the analogous lower bound.

MST-doubling algorithm

Step 1 — Build a minimum spanning tree $T$ of the complete weighted graph $G$.

Step 2 — Double every edge of $T$, producing a multigraph $H$ in which every vertex has even degree (each vertex's tree-degree is doubled, and even numbers stay even).

Step 3 — Find an Eulerian circuit in $H$. This exists because $H$ is connected (it contains $T$) and every vertex has even degree.

Step 4 — Shortcut the Eulerian circuit: walk it in order, and whenever it revisits a vertex already output, skip directly to the next new vertex, using the triangle inequality to justify that this skip does not increase total cost. The result is a Hamiltonian cycle. ``` MST-DOUBLE-TSP(G, w): // G: complete graph on vertex set V, w: edge weights satisfying triangle inequality T ← MST(G, w) // e.g., Prim's or Kruskal's algorithm H ← multigraph formed by duplicating every edge of T C ← EULERIAN-CIRCUIT(H) // exists: H connected, all degrees even tour ← [] visited ← empty set for v in C: if v not in visited: append v to tour add v to visited append tour[0] to tour // close the cycle return tour ```

Christofides' algorithm

The doubling step above is wasteful: it forces every edge to be traversed twice, even vertices that already had even degree. Christofides' refinement fixes only what is broken.

Step 1 — Build a minimum spanning tree $T$ of $G$.

Step 2 — Identify odd-degree vertices. Let $O$ be the set of vertices with odd degree in $T$. A handshake-lemma argument guarantees $|O|$ is even.

Step 3 — Compute a minimum-weight perfect matching $M$ on the vertices in $O$, using only edges of $G$ (the complete metric graph restricted to $O$).

Step 4 — Union $T$ and $M$. Every vertex in $O$ gains exactly one more incident edge from $M$, flipping its degree to even; vertices not in $O$ are untouched. The multigraph $T \cup M$ is connected and every vertex has even degree.

Step 5 — Find an Eulerian circuit in $T \cup M$, then shortcut exactly as before to obtain a Hamiltonian cycle. ``` CHRISTOFIDES-TSP(G, w): T ← MST(G, w) O ← { v ∈ V(T) : degree_T(v) is odd } M ← MIN-WEIGHT-PERFECT-MATCHING(G[O], w) // O(|O|^3) via Edmonds' blossom algorithm H ← multigraph union of T and M // all degrees now even C ← EULERIAN-CIRCUIT(H) tour ← [] visited ← empty set for v in C: if v not in visited: append v to tour add v to visited append tour[0] to tour return tour ``` The diagram below traces both repair strategies from the same spanning tree.

Both repaired multigraphs are Eulerian; the shortcutting step then converts the Eulerian circuit into a Hamiltonian cycle in $O(n)$ additional time. The difference between the two algorithms lies entirely in how much extra weight is added to make degrees even — doubling adds a full copy of $T$, while matching adds only enough edges to fix the (typically much smaller) set of odd-degree vertices.

Running time. Computing an MST takes $O(E \log V)$ with Prim's or Kruskal's algorithm, or $O(n^2)$ directly on a complete graph using a simple array-based Prim's implementation. Finding an Eulerian circuit takes $O(E)$ using Hierholzer's algorithm. Shortcutting is a single $O(n)$ pass. For MST-doubling, total time is dominated by the MST step: $O(n^2)$ on a dense metric instance. For Christofides, the additional cost is the minimum-weight perfect matching on the (at most $n$) odd-degree vertices, computable in $O(n^3)$ via Edmonds' blossom algorithm; this term dominates, giving overall $O(n^3)$.

Space is $O(n^2)$ to store the complete distance matrix, or $O(E)$ for the graph if sparse, plus $O(n)$ for the tree, tour, and auxiliary structures.

Correctness of the lower bound. Let OPT denote the weight of an optimal tour $C^*$. Removing any single edge from $C^*$ leaves a Hamiltonian path, which is in particular a spanning tree. Since the MST has minimum weight among all spanning trees,

This inequality is exact and requires no assumption about the metric — it is purely combinatorial.

Correctness of the shortcutting step. This is where the triangle inequality is essential. An Eulerian circuit visits every edge of $H$ exactly once, possibly revisiting vertices multiple times. When we skip from the last new vertex $u$ directly to the next new vertex $v$, bypassing already-visited vertices in between, the triangle inequality guarantees

by repeated application of $w(x,z) \le w(x,y) + w(y,z)$ along the path. Hence shortcutting never increases total cost: the final Hamiltonian cycle costs at most $w(H)$, the weight of the Eulerian multigraph.

MST-doubling ratio. The multigraph $H$ has weight $w(H) = 2 \cdot w(\text{MST})$. Combining the two facts above:

This proves the algorithm is a 2-approximation: it always outputs a tour of weight at most twice optimal, and this can be verified in polynomial time on any instance.

Christofides ratio — the extra argument. Let $O$ be the odd-degree vertices of the MST, and let $M$ be the minimum-weight perfect matching on $O$ found by the algorithm. We need $w(M) \le \tfrac{1}{2}\text{OPT}$. Consider the optimal tour $C^*$ restricted to the vertices of $O$ in the cyclic order they appear along $C^*$. Because $|O|$ is even, this cyclic sequence splits into two perfect matchings on $O$ by taking alternating edges (every other edge of the induced cycle). Concretely, if the vertices of $O$ appear along $C^*$ in order $v_1, v_2, \ldots, v_{2k}$ (with shortcut edges connecting them directly, again licensed by the triangle inequality), then $\{v_1v_2, v_3v_4, \ldots\}$ and $\{v_2v_3, v_4v_5, \ldots, v_{2k}v_1\}$ are two perfect matchings on $O$ whose combined weight is at most $w(C^*) = \text{OPT}$ (using the triangle inequality once more to bound the shortcut edges by the original tour segments they replace). Since these two matchings partition a cost of at most OPT, the cheaper one costs at most $\tfrac{1}{2}\text{OPT}$. As $M$ is the minimum-weight perfect matching on $O$, it costs no more than this cheaper one:

Now the Eulerian multigraph is $H = T \cup M$, with

Shortcutting again only decreases cost, so

This proves Christofides is a 3/2-approximation under the metric assumption.

Honesty about tradeoffs. The 3/2 bound is a worst-case guarantee, not a typical-case one; on many real instances both algorithms land within a few percent of optimal, and Christofides typically outperforms doubling in practice, not just in the worst-case bound. The price of the better ratio is a more expensive subroutine: blossom-algorithm matching is asymptotically and practically slower than an MST computation, and harder to implement correctly. Neither algorithm generalizes to non-metric TSP: without the triangle inequality, the shortcutting argument breaks entirely, since skipping a vertex could cost arbitrarily more than visiting it. Indeed, non-metric TSP has no polynomial-time constant-factor approximation unless P = NP, which is provable by a reduction from the Hamiltonian cycle problem that assigns weight 1 to real edges and an astronomically large weight to non-edges — any good approximation would have to distinguish Hamiltonian from non-Hamiltonian graphs.

Consider five points with Euclidean-style distances (satisfying the triangle inequality) laid out roughly as a pentagon with one interior point:

Step 1 — MST. Sorting edges: AB(2), CD(3), DE(4), BC(6), AE(7), BD(8), CE(8), AC(9), BE(9), AD(10). Running Kruskal's algorithm: add AB(2), add CD(3), add DE(4) [connects {C,D} with {D,E}, fine], next BC(6) connects {A,B} with {C,D,E} — add it. That is 4 edges for 5 vertices: MST = {AB, CD, DE, BC}, weight = 2+3+4+6 = 15. Degrees in the MST: A has degree 1 (to B), B has degree 2 (to A, C), C has degree 2 (to B, D), D has degree 2 (to C, E), E has degree 1 (to D). Odd-degree vertices: O = {A, E}.

Step 2a — MST-doubling. Double every MST edge: multigraph has AB, AB, BC, BC, CD, CD, DE, DE, total weight $2 \times 15 = 30$. An Eulerian circuit, e.g., A–B–C–D–E–D–C–B–A. Shortcutting (skip repeats): A, B, C, D, E, back to A. Tour cost: $w(AB)+w(BC)+w(CD)+w(DE)+w(EA) = 2+6+3+4+7 = \mathbf{22}$. Check against the bound: $2 \times \text{MST} = 30 \ge 22$, and since $\text{MST} \le \text{OPT}$, we know $\text{OPT} \ge 15$, so the guarantee $22 \le 2 \times \text{OPT}$ holds regardless of OPT's exact value.

Step 2b — Christofides. $O = \{A, E\}$, and since $|O|=2$ there is only one possible perfect matching: the single edge $AE$, weight 7. This is trivially the minimum-weight perfect matching on $O$. Union $T \cup M$ = {AB, BC, CD, DE, AE}, weight $15 + 7 = 22$. Every vertex now has even degree (A: 2, B: 2, C: 2, D: 2, E: 2) — in fact this multigraph is already a single cycle: A–B–C–D–E–A. The Eulerian circuit is the Hamiltonian cycle already, no shortcutting needed. Tour cost: $2+6+3+4+7 = \mathbf{22}$. In this small instance both algorithms happen to produce the identical tour of cost 22 (the MST plus one connecting edge was already Hamiltonian), and in fact the brute-force optimum here is also 22 — verified by checking all $4!/2 = 12$ distinct tours through the 5 points, none of which beats 22. This coincidence is typical of tiny instances; on larger graphs Christofides' extra matching step routinely produces a strictly cheaper repair than blind doubling, since $w(M) \le \tfrac12 w(T)$ is common while doubling always pays the full $w(T)$ again.

The Traveling Salesman Problem's approximability was shaped by the broader development of NP-completeness theory and combinatorial optimization in the 1970s. Nicos Christofides introduced the matching-based repair in 1976 as a technical report, and it stood for decades as the best known approximation ratio for metric TSP — a striking testament to how a conceptually simple idea (patch only what's broken) can resist improvement for so long. The MST-doubling idea, while simpler, reflects the same era's realization that spanning trees give clean, computable lower bounds for tour problems.

Metric TSP approximations underpin vehicle routing software used by logistics companies to plan delivery sequences, since real road-network distances (or their shortest-path approximations) satisfy the triangle inequality. Circuit board manufacturing uses TSP approximations to sequence drill-head movements across thousands of holes, where Euclidean travel time is the metric. Genome sequencing pipelines have historically used TSP-style tours to order DNA fragments by similarity. Christofides-style repair is also a template beyond TSP itself: the general pattern — cheap lower-bound structure, augment to satisfy a parity or connectivity constraint, exploit a metric or submodular property to bound the augmentation cost — recurs in network design approximations and facility location. These same algorithms serve as the natural baseline against which more elaborate Heuristics and Local Search methods, such as 2-opt, Lin-Kernighan, and simulated annealing, are measured, since a local-search heuristic with no guarantee is only convincing once compared against a provable worst-case bound like Christofides'.

Ask the tutor: How does the proof that $w(M) \le \tfrac12 \text{OPT}$ change if the odd-degree vertex set $O$ is very large relative to $n$?