Christofides Metric Tour Parity Certificate

worked-example

Consider the Square point fixture, where vertices are at (0,0), (2,0), (2,2), (0,2).

1. Compute the Minimum Spanning Tree (MST): Edges: (0,1) weight 2, (1,2) weight 2, (2,3) weight 2. Total MST weight = 6. 2. Identify odd-degree vertices in the MST: Vertices 0 and 3 have degree 1 (odd). 3. Find the minimum-weight perfect matching among odd vertices: Match (0,3). Cost = 2. 4. Combine MST and matching into a multigraph. Euler circuit: 0-1-2-3-0. 5. Shortcut the circuit to form a valid TSP tour: Tour: 0,1,2,3,0. Total Cost = 8. Exact Optimum = 8. Approximation Ratio = 1.0 (≤ 1.5).

experiment

You can interactively explore the algorithm on different metric point sets.

1. Select the Point fixture to Asymmetric6.
2. Set the Start vertex to 2.
3. Observe the MST, the identified odd vertices, the perfect matching, and the final shortcut tour cost.
4. Verify that the Tour Cost is certified to be within 1.5 times the Exact Optimum.

Interactive Title

limitations

The 1.5-approximation ratio bound is guaranteed only for metric graphs, meaning the edge weights must satisfy the triangle inequality. If the graph is not metric, the shortcuts could arbitrarily increase the tour cost, and the approximation ratio would not hold. Furthermore, the problem is NP-hard, so computing the exact optimum for large networks is computationally infeasible.

references

For more details on the analysis of the Christofides algorithm and its approximation ratio bound, see the course lecture notes on approximation algorithms:
CMU CS 15-451: Approximation Algorithms.