Christofides Algorithm

A Bit of History

Nicos Christofides, a Cypriot-British operational researcher, described this algorithm in a 1976 technical report at Carnegie Mellon University — and, in an unusual quirk of academic history, never formally published it in a peer-reviewed journal for decades, even as it became one of the most cited and taught results in combinatorial optimization, circulated informally among researchers who recognized its significance long before any formal publication. For over 40 years it stood as the best known polynomial-time approximation guarantee for metric TSP, until a 2020 paper by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan achieved a very slightly better (though still \(3/2 - \epsilon\) for a tiny \(\epsilon\)) bound — a reminder that even 44-year-old landmark results can eventually be nudged forward by new techniques.

Working Principle

Christofides' algorithm applies only to metric TSP — instances where distances satisfy the triangle inequality (\(d(a,c) \leq d(a,b) + d(b,c)\)) — and combines three algorithms already covered in this series into one guaranteed-quality tour:

1. Build a Minimum Spanning Tree \(T\) of the graph (via Prim's or Kruskal's algorithm from earlier deep dives).
2. Find all odd-degree vertices in \(T\). By the Handshake Lemma (Part 4), there is always an even number of them.
3. Compute a minimum-weight perfect matching \(M\) on just those odd-degree vertices (via the Blossom Algorithm, since this matching is not necessarily bipartite — see the next deep dive), and add \(M\)'s edges to \(T\), producing a multigraph where every vertex now has even degree.
4. Find an Eulerian circuit on this multigraph (via Hierholzer's algorithm, previewed for the next deep dive) — guaranteed to exist by Euler's own theorem from Part 12, since every vertex now has even degree.
5. Shortcut the Eulerian circuit into a Hamiltonian cycle by skipping any already-visited vertex, using the triangle inequality to guarantee skipping never increases total distance.

Worked Example

Consider 5 points roughly forming a pentagon. The MST connects them with 4 edges forming a tree (say, a "star" or "path" shape depending on exact distances); in a path-shaped MST, exactly the two endpoints have odd degree (degree 1) — everything else has even degree. Matching those two odd-degree endpoints directly (a trivial 1-edge matching, since there are only two of them) and adding that edge to the tree creates a multigraph where every vertex has even degree, so an Eulerian circuit exists trivially by simply traversing the tree and returning via the matching edge. Shortcutting (skipping repeats) then reconstructs a valid tour of all 5 cities.

Why 3/2 Is Guaranteed

The approximation guarantee follows from comparing three quantities. Let \(OPT\) be the optimal tour cost. Since removing any single edge from the optimal tour produces a spanning tree, the MST cost satisfies \(w(T) \leq OPT\). The minimum-weight matching on the odd-degree vertices costs at most half the optimal tour's cost restricted to those vertices — a clever argument using the fact that the optimal tour, restricted to just the odd-degree vertices in order, splits into two matchings whose combined weight is at most \(OPT\), so the cheaper of the two is at most \(OPT/2\): \(w(M) \leq OPT/2\). Combining:

$$w(T) + w(M) \leq OPT + \frac{OPT}{2} = \frac{3}{2}OPT$$

The Eulerian circuit built from \(T \cup M\) costs exactly \(w(T)+w(M)\), and the triangle inequality guarantees shortcutting can only decrease (never increase) the total distance — so the final tour costs at most \(\frac{3}{2}OPT\), guaranteeing the algorithm is never more than 50% worse than optimal.

Complexity Analysis

Each stage runs in polynomial time — MST construction \(O(E \log V)\), minimum-weight perfect matching on the odd-degree vertices (the bottleneck) \(O(V^3)\) via classical implementations of the Blossom Algorithm, and Hierholzer's Eulerian circuit \(O(E)\):

$$\text{Time: } O(V^3) \qquad \text{(dominated by the minimum-weight matching step)}$$

This is polynomial — a dramatic contrast with Held-Karp's exponential exact solving, at the cost of only guaranteeing a 3/2-approximation rather than the true optimum.

Implementation

import itertools

def christofides_sketch(dist, n):
    """
    Simplified sketch (small-n brute-force matching) illustrating the algorithm's
    stages. Production implementations use Prim's MST + Blossom Algorithm matching
    + Hierholzer's circuit, each covered as their own deep dives in this series.
    """
    # Step 1: Minimum Spanning Tree via a simple Prim's implementation
    in_tree = [False] * n
    in_tree[0] = True
    tree_edges = []
    for _ in range(n - 1):
        best = (float('inf'), -1, -1)
        for u in range(n):
            if not in_tree[u]:
                continue
            for v in range(n):
                if not in_tree[v] and dist[u][v] < best[0]:
                    best = (dist[u][v], u, v)
        tree_edges.append((best[1], best[2]))
        in_tree[best[2]] = True

    # Step 2: Find odd-degree vertices in the tree
    degree = [0] * n
    for u, v in tree_edges:
        degree[u] += 1
        degree[v] += 1
    odd_vertices = [v for v in range(n) if degree[v] % 2 == 1]

    # Step 3: Minimum-weight perfect matching on odd vertices (brute force for small n)
    def min_matching(vertices):
        if not vertices:
            return 0, []
        first, rest = vertices[0], vertices[1:]
        best_cost, best_pairs = float('inf'), []
        for i, partner in enumerate(rest):
            remaining = rest[:i] + rest[i+1:]
            sub_cost, sub_pairs = min_matching(remaining)
            cost = dist[first][partner] + sub_cost
            if cost < best_cost:
                best_cost, best_pairs = cost, [(first, partner)] + sub_pairs
        return best_cost, best_pairs

    _, matching_edges = min_matching(odd_vertices)

    # Step 4 + 5: Combine, find Eulerian circuit, shortcut (simplified for sketch)
    multigraph_edges = tree_edges + matching_edges
    return multigraph_edges  # feed into Hierholzer's algorithm + shortcutting

dist = [
    [0, 10, 15, 20, 25],
    [10, 0, 35, 25, 30],
    [15, 35, 0, 30, 20],
    [20, 25, 30, 0, 15],
    [25, 30, 20, 15, 0],
]
print(christofides_sketch(dist, 5))

#include <vector>
#include <limits>
#include <iostream>
using namespace std;

// Step 1: Minimum Spanning Tree via simple Prim's (see Prim deep dive for full version)
vector<pair<int,int>> buildMST(vector<vector<int>>& dist, int n) {
    vector<bool> inTree(n, false);
    inTree[0] = true;
    vector<pair<int,int>> treeEdges;
    for (int iter = 0; iter < n - 1; iter++) {
        int bestCost = INT_MAX, bu = -1, bv = -1;
        for (int u = 0; u < n; u++) {
            if (!inTree[u]) continue;
            for (int v = 0; v < n; v++) {
                if (!inTree[v] && dist[u][v] < bestCost) {
                    bestCost = dist[u][v]; bu = u; bv = v;
                }
            }
        }
        treeEdges.push_back({bu, bv});
        inTree[bv] = true;
    }
    return treeEdges;
}

// Step 2: Odd-degree vertices (Steps 3-5 — matching + Eulerian circuit — use the
// Blossom Algorithm and Hierholzer's algorithm deep dives in this series)
vector<int> oddDegreeVertices(vector<pair<int,int>>& treeEdges, int n) {
    vector<int> degree(n, 0);
    for (auto& e : treeEdges) { degree[e.first]++; degree[e.second]++; }
    vector<int> odd;
    for (int v = 0; v < n; v++) if (degree[v] % 2 == 1) odd.push_back(v);
    return odd;
}

int main() {
    vector<vector<int>> dist = {
        {0, 10, 15, 20, 25}, {10, 0, 35, 25, 30}, {15, 35, 0, 30, 20},
        {20, 25, 30, 0, 15}, {25, 30, 20, 15, 0}
    };
    int n = dist.size();
    auto treeEdges = buildMST(dist, n);
    auto odd = oddDegreeVertices(treeEdges, n);
    cout << "Odd-degree vertices: ";
    for (int v : odd) cout << v << " ";
    cout << endl;
    return 0;
}

import java.util.*;

class ChristofidesSketch {
    // Step 1: Minimum Spanning Tree via simple Prim's (see Prim deep dive for full version)
    static List<int[]> buildMST(int[][] dist, int n) {
        boolean[] inTree = new boolean[n];
        inTree[0] = true;
        List<int[]> treeEdges = new ArrayList<>();
        for (int iter = 0; iter < n - 1; iter++) {
            int bestCost = Integer.MAX_VALUE, bu = -1, bv = -1;
            for (int u = 0; u < n; u++) {
                if (!inTree[u]) continue;
                for (int v = 0; v < n; v++) {
                    if (!inTree[v] && dist[u][v] < bestCost) {
                        bestCost = dist[u][v]; bu = u; bv = v;
                    }
                }
            }
            treeEdges.add(new int[]{bu, bv});
            inTree[bv] = true;
        }
        return treeEdges;
    }

    // Step 2: Odd-degree vertices (Steps 3-5 use the Blossom Algorithm and
    // Hierholzer's algorithm deep dives in this series)
    static List<Integer> oddDegreeVertices(List<int[]> treeEdges, int n) {
        int[] degree = new int[n];
        for (int[] e : treeEdges) { degree[e[0]]++; degree[e[1]]++; }
        List<Integer> odd = new ArrayList<>();
        for (int v = 0; v < n; v++) if (degree[v] % 2 == 1) odd.add(v);
        return odd;
    }

    public static void main(String[] args) {
        int[][] dist = {
            {0, 10, 15, 20, 25}, {10, 0, 35, 25, 30}, {15, 35, 0, 30, 20},
            {20, 25, 30, 0, 15}, {25, 30, 20, 15, 0}
        };
        int n = dist.length;
        List<int[]> treeEdges = buildMST(dist, n);
        List<Integer> odd = oddDegreeVertices(treeEdges, n);
        System.out.println("Odd-degree vertices: " + odd);
    }
}

Real-World Applications

Exercises

1. Verify by hand that the Handshake Lemma guarantees an even number of odd-degree vertices in any spanning tree, and explain why this is essential for Christofides' algorithm to work at all.
2. Explain in your own words why the minimum-weight matching step specifically needs the (non-bipartite) Blossom Algorithm rather than Hopcroft-Karp, referencing the "odd-degree vertices" set the matching is computed on.
3. Trace through the 5-city worked example by hand: build the MST, identify odd-degree vertices, match them, and shortcut the resulting Eulerian circuit into a final tour.
4. Challenge: Research the 2020 Karlin-Klein-Oveis Gharan result that slightly improved on the 3/2 bound, and summarize (at a high level) what new technique enabled the improvement after 44 years.

Limitations