R9. Approximation Algorithms: Traveling Salesman Problem

What this lecture covers

This recitation works through approximation algorithms for the traveling salesman problem (TSP), building on a lecture about approximation algorithms in general. Since even constant-factor approximation of general TSP is NP-hard, the session restricts to metric TSP, where edge weights satisfy the triangle inequality, and derives two classic approximations: a simple 2-approximation based on a minimum spanning tree, and an improved 3/2-approximation (Christofides-style) that adds a minimum-cost perfect matching before extracting an Euler circuit.

The recitation sits alongside the main lecture on approximation algorithms and assumes familiarity with minimum spanning trees, bipartite matching, and NP-hardness. After working through it, you should be able to explain why the triangle inequality lets you "shortcut" repeated vertices without increasing cost, derive the 2-approximation from a DFS traversal of a spanning tree, and follow the more involved argument that combines a spanning tree with a minimum-cost perfect matching on odd-degree vertices to get a 3/2-approximation.

Key ideas

• Metric TSP: a version of TSP where distances are symmetric, positive, and obey the triangle inequality, making constant-factor approximation possible even though general TSP approximation is NP-hard.
• Shortcutting: given the triangle inequality, skipping over a repeated or unwanted vertex in a walk never increases total cost, which lets you turn a closed walk that revisits vertices into a valid Hamiltonian cycle.
• Spanning tree lower bound: removing one edge from the optimal Hamiltonian cycle yields a spanning tree, so the minimum spanning tree's cost is always at most the optimal tour's cost.
• 2-approximation: doing a DFS traversal of a minimum spanning tree traverses every edge twice, then shortcutting duplicate vertices gives a cycle of cost at most 2 * cost(MST) <= 2 * cost(optimal tour).
• Perfect matching: a set of edges giving every vertex exactly one incident edge, requiring an even number of vertices, computable in polynomial time on a complete graph.
• Euler circuit condition: a graph has a closed walk using every edge exactly once if and only if every vertex has even degree.
• Odd-degree fix: in any graph the number of odd-degree vertices is even (since the sum of degrees is 2|E|), so a minimum-cost perfect matching on just the odd-degree vertices can be added to a tree to make every degree even.
• 3/2-approximation: adding a minimum matching on the tree's odd-degree vertices costs at most half the optimal tour (since splitting the optimal tour's restriction to those vertices into two matchings bounds the minimum matching), giving total cost at most 1.5 * cost(optimal tour).

Walkthrough

Setting up metric TSP and the cost notation (1:00)

The recitation reviews why TSP approximation is generally NP-hard, then restricts to the metric case, where the triangle inequality holds. It defines C(S) as the total weight of a multiset of edges S, and frames the goal as approximating H*(G), the minimum-weight Hamiltonian cycle, since that's a harder problem than simply finding a Hamiltonian cycle.

Building the 2-approximation from a spanning tree (4:03)

Since finding a Hamiltonian cycle directly is hard, the recitation starts from a minimum spanning tree, which is computable in polynomial time and connects all vertices. Rooting the tree and doing a DFS traversal visits every vertex, but each tree edge gets traversed twice (once down, once back up), and vertices are revisited. The recitation shows that removing duplicate vertices via shortcutting, licensed by the triangle inequality, turns this walk into a valid Hamiltonian cycle without increasing cost.

Proving the 2-approximation bound (8:04)

The DFS traversal cost is exactly 2 * cost(T), where T is the minimum spanning tree, since every tree edge is crossed twice. Removing an edge from the optimal Hamiltonian cycle produces some spanning tree, so cost(T) <= cost(H*(G)). Chaining these inequalities gives cost(C') <= 2 * cost(H*(G)), establishing the 2-approximation.

Restricting the graph to a vertex subset (12:09)

A lemma states that for any subset S of vertices, the optimal Hamiltonian cycle restricted to S costs no more than the optimal Hamiltonian cycle on the full graph. The proof is by contradiction: if a cheaper cycle existed just for S, you could shortcut the full optimal cycle down to only the vertices of S and get an even cheaper cycle covering S, using the same triangle-inequality shortcutting technique.

Perfect matchings and Euler circuits (15:12)

The recitation introduces perfect matchings on complete graphs (solvable in polynomial time via methods related to linear programming) and Euler circuits: a graph has a closed walk traversing every edge exactly once if and only if every vertex has even degree. It notes that a spanning tree typically has many odd-degree vertices, which blocks a direct Euler circuit.

Fixing odd degrees with a minimum matching (19:17)

Since the sum of all vertex degrees is 2|E|, the number of odd-degree vertices in any graph is always even. The recitation restricts the graph to just the odd-degree vertices, computes a minimum-cost perfect matching M on them, and adds M's edges to the spanning tree T. The resulting multigraph T union M has every vertex at even degree, so it has an Euler circuit.

Deriving the 3/2-approximation bound (25:19)

The Euler circuit's cost is cost(T) + cost(M), and shortcutting duplicates gives a valid Hamiltonian cycle with cost at most this sum. The spanning tree term is bounded as before by cost(H*(G)). For the matching term, the recitation restricts to the odd-degree set S, notes that the optimal Hamiltonian cycle on S splits into two matchings M1 and M2 by taking alternating edges, and since M is the minimum-cost matching on S, cost(M) <= (cost(M1) + cost(M2)) / 2 = cost(H*(S)) / 2 <= cost(H*(G)) / 2. Adding the two bounds gives total cost at most 1.5 * cost(H*(G)), the 3/2-approximation.

Before you watch

• Review minimum spanning tree algorithms and why they run in polynomial time.
• Be familiar with bipartite matching and the idea of minimum-cost perfect matching on a complete graph.
• Know what NP-hardness means and why general TSP approximation is NP-hard, covered in the main approximation algorithms lecture this recitation follows.

Check your understanding

1. Why does the triangle inequality guarantee that shortcutting a repeated vertex in a walk never increases the total cost?
2. Explain why removing one edge from the optimal Hamiltonian cycle always produces a spanning tree, and why this bounds the minimum spanning tree's cost.
3. Why must the number of odd-degree vertices in any graph always be even?
4. Walk through why splitting the optimal Hamiltonian cycle on the odd-degree vertices into two alternating matchings bounds the cost of the minimum-cost perfect matching on those vertices.
5. Combine the two bounds to show why the Euler-circuit-based algorithm achieves a 3/2-approximation rather than the earlier 2-approximation.