Christofides Algorithm

The Metric TSP Promise

Christofides solves the symmetric metric TSP: the graph is complete, edge costs are nonnegative and symmetric, and every triple obeys the triangle inequality

The output is a Hamiltonian cycle, and its cost is guaranteed to be at most $3/2$ times the optimal tour cost. The promise matters: symmetry supports undirected matching, and the triangle inequality makes shortcutting repeated vertices safe.

Intuition: Backbone and Parity Repair

A minimum spanning tree is cheap and reaches every city, but it is not a tour. Doubling every tree edge would make all degrees even and yield the familiar $2$-approximation. Christofides is more selective: only odd-degree vertices prevent an Eulerian circuit, so it pays for the cheapest perfect matching that fixes exactly those parity defects.

The Algorithm Pipeline

1. Compute a minimum spanning tree $T$.
2. Collect the set $O$ of vertices having odd degree in $T$.
3. Find a minimum-weight perfect matching $M$ in the complete graph induced by $O$.
4. Combine $T$ and $M$ as a multigraph. Parallel copies must remain distinct.
5. Find an Eulerian circuit in $T\cup M$.
6. Scan the circuit and skip already visited vertices, then return to the start.

Adding $M$ flips the parity of every vertex in $O$. The even-degree tree vertices are untouched, and the odd-degree vertices become even. The combined multigraph stays connected because it still contains the spanning tree, so an Eulerian circuit exists.

A Five-City Metric Trace

Consider a center city $0$ at Manhattan distance $1$ from four surrounding cities; every pair of surrounding cities is distance $2$. This is a genuine metric instance.

Why Shortcutting Works

The Eulerian circuit may revisit vertices because it traverses every multigraph edge exactly once. Scan its vertex sequence and keep only each vertex's first appearance. Whenever a repeated block is skipped, replace a path $a\to b\to\cdots\to c$ with the direct edge $a\to c$.

Repeated application of the triangle inequality proves the direct jump cannot cost more. In the example, the Euler segment $2\to0\to3$ costs $1+1=2$, while shortcut $2\to3$ also costs $2$.

The $3/2$ Approximation Proof

Let $OPT$ be the cost of an optimal metric tour.

1. The tree uses at most one $OPT$ budget

Deleting any edge from the optimal tour leaves a spanning tree. Since $T$ is minimum among all spanning trees,

2. Parity repair uses at most half an $OPT$ budget

List the odd-degree vertices $O$ in the order they appear on the optimal tour and shortcut between consecutive members. Triangle inequality gives a cycle on $O$ of cost at most $OPT$. Because $|O|$ is even, alternating edges of that cycle form two perfect matchings. Their total is at most $OPT$, so the cheaper one costs at most $OPT/2$. The algorithm chooses the minimum perfect matching, hence $w(M)\le OPT/2$.

3. Euler and shortcut steps spend no extra budget

The Eulerian circuit uses every edge of $T\cup M$ exactly once, so it costs $w(T)+w(M)$. Shortcutting cannot increase cost. Therefore

Implementation

The Python tab is a complete educational implementation. To remain dependency-free, it finds the odd-set matching with exponential subset recursion, so the resulting program is appropriate only for small instances. A production polynomial-time implementation must replace that helper with a minimum-weight perfect-matching algorithm such as weighted Blossom. The C++ and Java tabs show the MST/parity scaffold where those production subroutines connect.

from functools import lru_cache

def christofides_small(dist):
    """Complete educational Christofides implementation for a small metric."""
    n = len(dist)
    if n == 0 or any(len(row) != n for row in dist):
        raise ValueError("dist must be a nonempty square matrix")
    if n == 1:
        return {"tour": [0, 0], "cost": 0, "mst": [], "odd": [], "matching": []}

    # Validate the symmetric metric promise.
    for i in range(n):
        if dist[i][i] != 0:
            raise ValueError("diagonal costs must be zero")
        for j in range(n):
            if dist[i][j] < 0 or abs(dist[i][j] - dist[j][i]) > 1e-9:
                raise ValueError("dist must be nonnegative and symmetric")
            for k in range(n):
                if dist[i][k] > dist[i][j] + dist[j][k] + 1e-9:
                    raise ValueError("triangle inequality is violated")

    # 1. Dense Prim MST.
    in_tree = [False] * n
    key = [float("inf")] * n
    parent = [-1] * n
    key[0] = 0
    for _ in range(n):
        u = min((v for v in range(n) if not in_tree[v]), key=key.__getitem__)
        in_tree[u] = True
        for v in range(n):
            if not in_tree[v] and dist[u][v] < key[v]:
                key[v], parent[v] = dist[u][v], u
    tree_edges = [(parent[v], v) for v in range(1, n)]

    # 2. Odd-degree set.
    degree = [0] * n
    for u, v in tree_edges:
        degree[u] += 1
        degree[v] += 1
    odd = [v for v in range(n) if degree[v] % 2]

    # 3. Exact minimum perfect matching by DP over the odd set.
    # Replace this exponential helper with weighted Blossom in production.
    @lru_cache(None)
    def match(mask):
        if mask == 0:
            return 0, ()
        first = (mask & -mask).bit_length() - 1
        remaining = mask ^ (1 << first)
        best_cost, best_pairs = float("inf"), ()
        candidates = remaining
        while candidates:
            partner = (candidates & -candidates).bit_length() - 1
            sub_cost, sub_pairs = match(remaining ^ (1 << partner))
            candidate = dist[odd[first]][odd[partner]] + sub_cost
            if candidate < best_cost:
                best_cost = candidate
                best_pairs = ((odd[first], odd[partner]),) + sub_pairs
            candidates ^= 1 << partner
        return best_cost, best_pairs

    _, matching_tuple = match((1 << len(odd)) - 1)
    matching_edges = list(matching_tuple)

    # 4. Eulerian circuit. Edge IDs preserve parallel copies.
    edges = tree_edges + matching_edges
    adjacency = [[] for _ in range(n)]
    for edge_id, (u, v) in enumerate(edges):
        adjacency[u].append((v, edge_id))
        adjacency[v].append((u, edge_id))

    used = [False] * len(edges)
    stack, circuit = [0], []
    while stack:
        v = stack[-1]
        while adjacency[v] and used[adjacency[v][-1][1]]:
            adjacency[v].pop()
        if not adjacency[v]:
            circuit.append(stack.pop())
        else:
            neighbor, edge_id = adjacency[v].pop()
            used[edge_id] = True
            stack.append(neighbor)
    circuit.reverse()

    # 5. Keep first visits, then close the Hamiltonian cycle.
    seen, tour = set(), []
    for v in circuit:
        if v not in seen:
            seen.add(v)
            tour.append(v)
    tour.append(tour[0])
    tour_cost = sum(dist[tour[i]][tour[i + 1]] for i in range(n))
    return {"tour": tour, "cost": tour_cost, "mst": tree_edges,
            "odd": odd, "matching": matching_edges, "euler": circuit}

dist = [
    [0, 1, 1, 1, 1],
    [1, 0, 2, 2, 2],
    [1, 2, 0, 2, 2],
    [1, 2, 2, 0, 2],
    [1, 2, 2, 2, 0],
]
result = christofides_small(dist)
print(result["tour"], result["cost"])  # one valid answer: [0, 4, 3, 2, 1, 0] 8

#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 = numeric_limits<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,1,1,1,1}, {1,0,2,2,2}, {1,2,0,2,2},
        {1,2,2,0,2}, {1,2,2,2,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,1,1,1,1}, {1,0,2,2,2}, {1,2,0,2,2},
            {1,2,2,0,2}, {1,2,2,2,0}
        };
        int n = dist.length;
        List<int[]> treeEdges = buildMST(dist, n);
        List<Integer> odd = oddDegreeVertices(treeEdges, n);
        System.out.println("Odd-degree vertices: " + odd);
    }
}

Complexity

For sparse input networks, first computing a metric closure may itself require all-pairs shortest paths. The relevant total cost then includes both closure construction and Christofides on the resulting complete distance graph.

Where the Guarantee Applies

A tour still comes out if the program is fed a nonmetric matrix, but the $3/2$ statement no longer follows. Approximation guarantees are contracts: every assumption in the theorem is part of the input specification.

Common Pitfalls and a Reliable Checklist

Where Christofides Is Useful

• Guaranteed baseline: compare heuristic or learned tours against a solution with a proven metric bound.
• Local-search initializer: begin from a structured tour, then improve it without losing feasibility.
• Small-instance study: compare Christofides with exact Held–Karp to measure the observed approximation ratio.
• Algorithm composition: study how MST, parity, matching, Euler traversal, and metric shortcutting cooperate in one proof.

Exercises

1. Parity: prove that the odd-degree set of every tree has even cardinality.
2. Trace: reproduce the five-city pipeline, including vertex degrees before and after matching.
3. Euler choices: find a different Eulerian circuit in the same multigraph and shortcut it. Does the tour change?
4. Proof: draw an eight-vertex odd-set cycle and split its edges into two perfect matchings.
5. Counterexample: construct three nonmetric costs where shortcut $a\to c$ is more expensive than $a\to b\to c$.
6. Verification: generate small Euclidean instances, compare the Python tour with exact Held–Karp, and assert the ratio never exceeds $1.5$.

History and Takeaway

Nicos Christofides described the method in a 1976 technical report. Anatoliy Serdyukov discovered the same $3/2$ approach independently and published it in 1978, motivating the name Christofides–Serdyukov algorithm. Decades later, randomized work by Anna Karlin, Nathan Klein, and Shayan Oveis Gharan established a ratio of $3/2-\varepsilon$ for some $\varepsilon>10^{-36}$.