Christofides: Matching the Odd Vertices to Reach 3/2

The travelling salesman problem asks for the cheapest closed tour visiting every vertex of a complete graph exactly once. It is NP-hard, and no approximation with a constant factor exists for the general form: if edge weights can violate the triangle inequality, a single expensive edge can force any algorithm’s tour to be arbitrarily worse than optimal. Restricting to metric instances, where $w(u,v) \le w(u,x) + w(x,v)$ for all $x$, changes the situation. Christofides’ algorithm, published in 1976, gives a tour of cost at most $3/2$ times optimal in polynomial time, and that was the best known factor until Karlin, Klein and Oveis Gharan published an algorithm with ratio $3/2 - \varepsilon$ for a small absolute constant $\varepsilon$.

The algorithm has two stages, each with its own bound, and the bounds add. Understanding why the second stage is needed, and why it costs exactly half of the first stage’s slack, is the content of the analysis.

Stage one: spanning tree plus doubling

A tour is a connected spanning subgraph in which every vertex has degree 2. Removing any one edge of a tour leaves a spanning tree. Therefore the minimum spanning tree is a lower bound on the optimal tour:

$$ w(\mathrm{MST}) \le \mathrm{OPT} $$

That single inequality is the foundation of both stages. To turn a spanning tree into a tour, walk around it: perform a depth-first traversal, which visits every vertex and traverses every tree edge exactly twice, for total cost $2,w(\mathrm{MST})$. The walk visits vertices more than once, so it is not a tour; it is a closed walk of length $2(n-1)$ edges. Shortcut it by visiting vertices in the order of their first appearance and jumping directly between consecutive first-appearances. The metric inequality guarantees that each shortcut edge costs no more than the path it replaces, so the resulting tour has cost at most $2,w(\mathrm{MST}) \le 2,\mathrm{OPT}$.

This is the doubling algorithm, and it is a factor-2 approximation. The slack is easy to see: the depth-first walk traverses each tree edge twice, but a tour traverses the equivalent path structure once. Half the walk is redundant, and the shortcutting does not recover that half because it only removes repeats, not the second traversal of each edge.

Stage two: repairing parity

The 3/2 algorithm attacks the redundancy directly. Instead of duplicating every tree edge, duplicate only what is needed to make all degrees even.

A connected graph in which every vertex has even degree has an Eulerian circuit: a closed walk traversing every edge exactly once. So if a spanning tree could be augmented to even degrees, the Eulerian circuit would be a closed walk through all vertices, and shortcutting it would produce a tour. The parity defect of a tree is concentrated on the set $T$ of vertices with odd degree. In any graph, the number of odd-degree vertices is even (the handshake lemma), so $|T|$ is even, and a spanning tree has at least two such vertices — the leaves.

Adding a minimum-weight perfect matching on $T$ to the tree fixes every degree: matched vertices gain one, unmatched vertices are unchanged and were already even. The result is connected (it contains the tree), all degrees are even, and an Eulerian circuit exists. Shortcut it and the cost is

$$ w(\mathrm{MST}) + w(\text{matching on } T) $$

The question becomes how large the matching can be, and the answer comes from the optimal tour itself.

Bounding the matching by half the optimum

Take an optimal tour $H$, and delete from it every vertex not in $T$. What remains is a cycle through the vertices of $T$ in the order they appear along $H$. Because $|T|$ is even, this cycle has even length and can be split into two perfect matchings on $T$: take alternate edges around the cycle. The two matchings together use exactly the edges of the cycle, so their total cost is at most the cost of the cycle, which is at most $w(H) = \mathrm{OPT}$ because shortcutting $H$ along $T$ cannot increase cost under the metric inequality. One of the two matchings therefore has cost at most $\mathrm{OPT}/2$. Since the algorithm uses a minimum-weight perfect matching on $T$, its cost is no larger:

$$ w(\text{min matching on } T) \le \frac{\mathrm{OPT}}{2} $$

Adding the two bounds gives $w(\mathrm{MST}) + w(\text{matching}) \le \mathrm{OPT} + \mathrm{OPT}/2 = \tfrac{3}{2}\mathrm{OPT}$, and shortcutting the Eulerian circuit cannot increase cost, so the tour is within $3/2$ of optimal.

Both stages spend the metric inequality, and they spend it in different places. Stage one spends it when shortcutting repeated vertices: the direct edge between two first-visits is no longer than the walk between them. Stage two spends it twice, once when shortcutting the optimal tour to the odd set and once when shortcutting the Eulerian circuit. Without the inequality, neither shortcut is valid, and the factor-2 and factor-3/2 claims both collapse.

The algorithm in outline

The construction is a fixed sequence of five steps, and the analysis above pins down each one.

1. Compute a minimum spanning tree of the cost matrix.
2. Collect the set $T$ of vertices whose degree in that tree is odd.
3. Compute a minimum-weight perfect matching on the complete graph induced by $T$.
4. Take the union of the tree and the matching. Every degree is now even and the graph is connected.
5. Find an Eulerian circuit of that multigraph and shortcut it, keeping each vertex the first time it appears.

Steps 2 and 5 are bookkeeping over a graph with $O(n)$ edges. Step 1 is the cheapest of the three substantive steps. Step 3 is where the implementation effort goes. The spanning tree is $O(n^2)$ with Prim on a dense matrix, or $O(m \log n)$ on a sparse graph. The matching is the expensive part: minimum-weight perfect matching in a general graph requires the blossom algorithm, and the standard implementation runs in $O(n^3)$ time on a complete graph with $n$ vertices. Since the odd set can contain all $n$ vertices, this is the dominant term, and it is why implementations of Christofides on large instances are rare despite the strength of the ratio.

The Eulerian circuit and the shortcut cost time linear in the number of edges, $n - 1 + |T|/2$, which is $O(n)$ and negligible beside the matching.

Why not simply match everything

A natural question is whether a better ratio comes from replacing the tree with something closer to a tour. The obvious candidate is a minimum-weight 2-matching: a set of edges in which every vertex has degree exactly 2, allowing several disjoint cycles. Its cost is a lower bound on the optimal tour, and a stronger one than the spanning tree’s. Starting the construction from it does not improve the ratio, for two reasons. All degrees are already even, so the parity repair that the matching step performs is vacuous, and the $1/2$ factor in that step’s bound has no counterpart. What remains instead is joining the disjoint cycles into one tour, and each join adds an edge whose weight the analysis cannot bound as a fraction of the optimum. The 2-matching is therefore useful as a lower bound and as a relaxation, not as the first stage of an algorithm.

The attack on $3/2$ that eventually succeeded took a different route: it strengthened the lower bound rather than the repair, replacing the spanning tree with the value of a linear program whose optimum is at least the tree’s cost and typically larger. The improvement that route yields is real but tiny, and the distance between the factors combinatorial analysis has reached and the $4/3$ that the subtour linear program’s integrality gap is known to permit is where the remaining work sits.

Where the ratio does not help

Three practical caveats limit the algorithm’s usefulness, and each follows from a specific assumption.

The metric assumption is strong. Distance matrices taken from road networks satisfy it, because shortest-path distances always do. But instances built from arbitrary costs, such as scheduling penalties or sequence alignment scores, need not, and applying Christofides to them invalidates the bound. The standard repair is to replace the cost matrix by its metric closure, the all-pairs shortest path distances, which makes the instance metric but changes the objective: a tour in the closure may use edges that do not exist in the original graph.

Asymmetric instances break it entirely. If $w(u,v) \ne w(v,u)$, the tour has a direction, the parity argument has no analogue because the Eulerian structure requires undirected edges, and the matching step is not well defined. The asymmetric problem has its own approximation algorithms, with worse factors, based on cycle covers and assignment problems.

The bound is worst-case and is not attained everywhere. On Euclidean instances, where vertices are points in the plane and costs are distances, both terms of the bound are loose for structural reasons: shortcutting the doubled walk removes most of the repeated traversal once a depth-first order’s successive first-visits lie close together, and the matching connects odd-degree vertices that a geometric placement tends to put near one another. Constructions that reach $3/2$ make both terms tight at once, which takes deliberate arrangement: the odd-degree set is large and no tree-plus-matching combination is nearly as cheap as the optimal tour. The bound is therefore a guarantee about every metric instance and a description of almost none of them.

The structural idea that carries forward

The pattern in Christofides recurs in other approximation results: find a combinatorial lower bound (the spanning tree), construct a feasible solution from it (the Eulerian circuit), and repair the defects (the matching) at a cost bounded by a fraction of the optimum using a structural argument about the optimal solution itself. The cut property argument for Kruskal supplies the first ingredient, and the matching step is where the problem-specific insight lives.

The same shape appears in the primal-dual schema, where a dual feasible solution bounds the primal optimum and the algorithm constructs a primal solution whose cost is a multiple of the dual. In Christofides the “dual” is the optimal tour itself, used only in the analysis and never computed. That is a common feature of combinatorial approximation proofs: the analysis reasons about an object the algorithm cannot construct, and the bound follows from the algorithm’s solution being at least as good as some constructed alternative.

The limit of this particular construction is the factor itself. Improving on $3/2$ within the same shape of argument requires either a better lower bound than the spanning tree or a cheaper repair than the matching. The repair route is closed: the analysis above is tight, because there are metric instances on which the spanning tree is optimal and a minimum-weight perfect matching on the odd-degree vertices costs half the tour, so no reformulation of the parity step recovers more. The lower-bound route is the one that worked, and it produced $3/2 - \varepsilon$ rather than anything an implementation would notice. A general limit on that route is known: the subtour linear program’s integrality gap is at least $4/3$, so no algorithm that certifies its tour against that program’s value can claim a factor below $4/3$.