JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Metric TSP and Christofides

The travelling salesman tour is NP-hard, but if distances obey the triangle inequality you can build a tour provably within a small factor of optimal. We walk from a clean 2-approximation up to the celebrated 1.5-factor of Christofides.

Why TSP needs a special assumption

The travelling salesman problem asks for the cheapest tour that visits every city exactly once and returns home. From the hardness rung you already know its cousin is brutal: deciding whether a graph even has a Hamiltonian cycle is NP-complete, so finding the cheapest Hamiltonian cycle is at least that hard. This is the moment the approximation mindset earns its keep: instead of an exact answer we will settle for a tour whose length is provably within a fixed factor of the best possible, the approximation ratio you met in guide 1 of this rung.

But there is a sting first. For general TSP, where edge costs can be anything, no constant-factor approximation can exist unless P = NP. The reason is a reduction: take any graph and ask whether it has a Hamiltonian cycle. Build a complete graph where original edges cost 1 and missing edges cost some gigantic M. A short tour exists exactly when the original graph is Hamiltonian, and by pumping M arbitrarily high you make the gap between "yes" and "no" as wide as you like. Any algorithm with a constant ratio would have to land on the right side of that gap, secretly solving the Hamiltonian cycle decision problem in polynomial time.

So we add an honest, mild restriction. In metric TSP the distances form a metric: every cost is nonnegative, the cost from a to b equals the cost from b to a, and for any three cities the triangle inequality holds, cost(a,c) <= cost(a,b) + cost(b,c). Going direct is never worse than detouring. This matches most real distances — driving times, Euclidean geometry — and, crucially, it gives us a lever the general problem denies: we are allowed to skip a city we have already visited and the bill never goes up.

The double-tree 2-approximation

Here is the first idea, and it is beautiful because it reuses something you already trust: the minimum spanning tree. Build the MST T of the cities (with Prim or Kruskal, your choice). A spanning tree connects everyone as cheaply as possible without forming a cycle, so it is almost a tour — it just is not a single loop. The plan: walk the tree, then shortcut the walk into a real tour. This is the double-tree algorithm.

  1. Build the MST T. Its total cost is cost(T).
  2. Double every edge of T. Now every vertex has even degree, so this multigraph has an Eulerian circuit — a closed walk using each (doubled) edge exactly once. Follow it; its length is exactly 2 * cost(T).
  3. Shortcut: walk the Eulerian circuit but skip any city you have already visited, jumping straight to the next new one. By the triangle inequality each skip can only shorten the trip. What remains visits every city once and returns home — a valid tour.

Now the analysis, and it is short. First, cost(T) <= OPT, where OPT is the optimal tour length. Why? Delete any one edge from the optimal tour and you get a path through all cities, which is a spanning tree; the MST is the cheapest spanning tree, so it cannot cost more than that path, which cannot cost more than the whole tour. Second, our tour costs at most the Eulerian walk, which is 2 * cost(T). Chaining them: tour <= 2 * cost(T) <= 2 * OPT. That is a clean 2-approximation — never more than twice optimal — and every step is something from earlier rungs.

Where the factor of 2 leaks

Look closely at where we lost ground. We compared our tour against OPT, but we threw away a factor of 2 in a single careless move: doubling every tree edge. We doubled because we needed every vertex to have even degree — that is the exact condition for an Eulerian circuit to exist. But doubling is a sledgehammer. We do not actually need the whole tree duplicated; we only need to fix the parity of the degrees.

In any graph the number of odd-degree vertices is always even (a classic handshake fact). So in the MST T, the vertices that have odd degree come in an even-sized set; call it O. If we could add a small set of extra edges that flips exactly those odd vertices to even — and leaves the already-even ones alone — we would have an Eulerian multigraph without paying for a second copy of the whole tree. The cheapest way to pair up the odd vertices and connect each pair is a minimum-weight perfect matching on O.

Christofides: the 1.5-factor

Putting the fix in place gives the Christofides algorithm, and it is just the double-tree algorithm with the wasteful doubling replaced by a thrifty matching. The whole method is four moves.

  1. Build the MST T of all cities.
  2. Let O be the set of odd-degree vertices of T (even in number). Compute a minimum-weight perfect matching M on O.
  3. Combine T and M into one multigraph. Adding M flips exactly the odd vertices' parity, so now every vertex has even degree and an Eulerian circuit exists. Trace it.
  4. Shortcut repeated cities using the triangle inequality, exactly as before, to get a valid tour.

The ratio is 1.5, and the bound has two ingredients. The first is the same as before: cost(T) <= OPT. The second is the new and clever one: cost(M) <= OPT / 2. Here is the picture. Restrict the optimal tour to just the cities in O and shortcut over the rest; by the triangle inequality this shrunken tour over O costs at most OPT. But a cycle through an even number of vertices splits into two perfect matchings (alternate edges, red and blue). One of those two matchings costs at most half the cycle, hence at most OPT / 2. Our M is the minimum matching on O, so it is no more expensive than that one: cost(M) <= OPT / 2.

Add the two pieces. The Eulerian multigraph costs cost(T) + cost(M) <= OPT + OPT/2 = 1.5 * OPT, and shortcutting only helps, so the final tour is at most 1.5 * OPT. That extra idea — fix parity with a matching instead of doubling — buys you the jump from factor 2 down to factor 1.5.

Honest limits and what to remember

Be precise about what 1.5 means. It is a worst-case guarantee: Christofides never returns a tour longer than 1.5 times optimal on a metric instance. It is not a claim about the typical case — on real maps it usually does far better, often within a few percent — but the proof only promises the ceiling, not the average. And the guarantee evaporates the instant the triangle inequality fails; on non-metric TSP, as we saw, no constant factor is possible at all unless P = NP.

How good can we ever hope to be? Metric TSP is APX-hard: there is a constant below which no polynomial-time approximation can go unless P = NP, so a PTAS for general metric TSP is ruled out. This is the flavour of inapproximability from later in this rung — hardness does not only block exact answers, it can also cap how closely you may approximate. Christofides stood as the best known ratio from 1976 for over four decades; only very recently was 1.5 nudged below by a hair, and the true best constant remains open.