06 Augmenting Paths, Hopcroft-Karp, 1.5 Approximation for Metric TSP

Video from: 06.03.2025 | Video: Homelab

Recall: Augmenting Paths and Maximum Matchings

Let’s begin by revisiting the fundamental concepts that underpin the Hopcroft-Karp algorithm. These ideas were introduced previously and are crucial for understanding the algorithm’s mechanics and correctness.

Augmenting Paths

Given a matching $M$ in a bipartite graph $G=(V,E)$, an augmenting path $P$ with respect to $M$ is a path in $G$ that satisfies the following conditions:

1. Alternating Path: The edges of $P$ are alternately in $M$ and not in $M$.
2. Unmatched Endpoints: Both the starting and ending vertices of $P$ are unmatched with respect to $M$, meaning they are not incident to any edge in $M$.

Augmenting a Matching

If we find an $M$-augmenting path $P$, we can increase the size of the matching by performing an augmentation. This is achieved by taking the symmetric difference of the current matching $M$ and the edges of the augmenting path $P$:

$M^{\prime }=M\oplus P=(M\cup P)\setminus (M\cap P)$

This operation effectively “flips” the status of edges along $P$: edges in $M\cap P$ are removed from the matching, and edges in $P\setminus M$ are added to the matching. The size of the matching increases by exactly one, i.e., $|M^{\prime }|=|M|+1$.

Berge’s Theorem

A cornerstone result in matching theory is Berge’s Theorem, which provides a necessary and sufficient condition for a matching to be maximum.

Berge’s Theorem: A matching $M$ in a graph $G$ is a maximum matching (i.e., has the largest possible cardinality) if and only if there is no $M$-augmenting path in $G$.

This theorem is critical because it gives us an algorithmic approach to finding maximum matchings. If our current matching is not maximum, Berge’s Theorem guarantees the existence of an augmenting path, which we can use to increase the matching size. We can repeat this process until no more augmenting paths can be found, at which point we have reached a maximum matching.

Basic Algorithm Sketch

Based on Berge’s Theorem, we can outline a basic algorithm for finding a maximum matching:

Algorithm Sketch:

Input: Bipartite Graph G = (V, E)
Output: Maximum Matching M
 
Initialize M = ∅ (empty matching)
while True:
    Search for an M-augmenting path P in G
    if no M-augmenting path P exists:
        return M  (M is a maximum matching)
    else:
        M = M ⊕ P  (augment the matching)

Finding Augmenting Paths in Bipartite Graphs using BFS

For bipartite graphs, we can efficiently search for augmenting paths using Breadth-First Search (BFS). The idea is to explore paths that alternate between edges not in the matching and edges in the matching.

BFS Approach to Find Augmenting Paths:

1. Start from Unmatched Vertices in Partition A: Begin the BFS from all vertices in partition $A$ that are currently unmatched. These vertices form the first layer (layer 0) of our BFS.

2. Alternating Layers:

   • Odd Layers (from A to B): From vertices in an even layer (say layer $i$, which is in partition $A$), explore edges that are not in the current matching $M$. Reach new vertices in partition $B$, which form the next layer (layer $i+1$, an odd layer).
   • Even Layers (from B to A): From vertices in an odd layer (say layer $i+1$, in partition $B$), explore edges that are in the current matching $M$. Reach new vertices in partition $A$, which form the next layer (layer $i+2$, an even layer).

3. Check for Unmatched Vertices in Partition B: During the BFS, if we reach an unmatched vertex in partition $B$ (say in layer $l$), we have found an augmenting path. This path can be traced back from this unmatched vertex to an unmatched vertex in partition $A$ (in layer 0) by following the predecessor pointers in the BFS tree.

4. Augment and Repeat: If an augmenting path is found, augment the matching and repeat the BFS process from step 1 with the new, larger matching.

5. Termination: If the BFS completes without finding any augmenting path (i.e., no unmatched vertex in $B$ is reached), then the current matching is maximum, and we terminate.

Inefficiency of Simple BFS Approach and Motivation for Hopcroft-Karp

While the BFS approach works, a naive implementation might perform redundant work in each iteration. Consider that in each iteration, we find only one augmenting path and increase the matching size by just one. We might need to repeat this process many times, potentially up to $|V|/2$ iterations in the worst case.

The inefficiency arises from the fact that we find and augment along only one augmenting path at a time, even if multiple disjoint augmenting paths might be available. This leads to potential duplicate work in subsequent BFS searches, as we might re-explore parts of the graph that could have been used to find other augmenting paths in the same iteration.

The Hopcroft-Karp algorithm addresses this inefficiency by finding a maximal set of shortest, vertex-disjoint augmenting paths in each iteration. By augmenting along all paths in this set simultaneously, it achieves a significantly faster runtime.

Hopcroft-Karp Algorithm: Finding Maximum Matching Efficiently

The Hopcroft-Karp algorithm is a more sophisticated approach to finding maximum matchings in bipartite graphs. It builds upon the idea of augmenting paths but optimizes the process by finding and augmenting along multiple augmenting paths in each iteration.

Algorithm Steps

Hopcroft-Karp Algorithm:

Input: Bipartite Graph G = (A ∪ B, E)
Output: Maximum Matching M
 
Initialize M = ∅ (empty matching)
repeat:
    1. BFS Phase:
        - Perform a BFS starting from all unmatched vertices in A.
        - Construct alternating paths, layer by layer.
        - Keep track of distances from unmatched vertices in A.
        - Let 'k' be the length of the shortest augmenting path found.
        - If no augmenting path is found, break the loop (M is maximum).
 
    2. DFS Phase:
        - Initialize a set S = ∅.
        - For each unmatched vertex 'u' in A:
            - Perform a DFS starting from 'u'.
            - Add each vertex-disjoint augmenting path of length 'k' to set S.
            - Continue DFS from 'u' until no more vertex-disjoint augmenting paths can be found.
 
    3. Augmentation:
        - For each augmenting path P in the set S:
            - M = M ⊕ P (augment the matching along path P)
 
until no augmenting paths are found in BFS phase
return M

Key Ideas in Hopcroft-Karp

1. Shortest Augmenting Paths: The algorithm focuses on finding shortest augmenting paths in each iteration. This is crucial for bounding the number of iterations.

2. Maximal Set of Vertex-Disjoint Paths: In each iteration, the algorithm finds a maximal set $S$ of vertex-disjoint augmenting paths of the shortest length. “Maximal” here means that we cannot add any more augmenting paths of the shortest length to $S$ while maintaining vertex-disjointness. It’s an inclusion-maximal set.

3. Simultaneous Augmentation: The algorithm augments the matching along all paths in the set $S$ in a single iteration. This is the key optimization that leads to the faster runtime.

Finding a Maximal Set of Vertex-Disjoint Augmenting Paths using DFS

The DFS phase is responsible for finding a maximal set $S$ of vertex-disjoint shortest augmenting paths. The process is as follows:

1. Iterate through Unmatched Vertices in A: For each unmatched vertex $u\in A$, initiate a DFS.

2. DFS for Shortest Paths: The DFS explores paths starting from $u$, respecting the alternating structure of augmenting paths and only considering paths of the shortest length $k$ (length determined by the BFS phase).

3. Vertex-Disjointness Enforcement: When a DFS finds an augmenting path $P$, we add $P$ to our set $S$. To ensure vertex-disjointness, once a vertex is included in a path in $S$, it should not be used in any other path added to $S$ in the same iteration. This can be managed by keeping track of vertices already used in paths in $S$ during the DFS.

4. Maximality: The DFS process, when iterated through all unmatched vertices in $A$, is designed to find a maximal set of vertex-disjoint shortest augmenting paths. While not necessarily a maximum set (in terms of cardinality of $S$), it is maximal in the sense that we cannot add another shortest augmenting path that is vertex-disjoint from all paths already in $S$.

Runtime of Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm achieves a significantly better runtime than the simple augmenting path algorithm. The key result is that the number of iterations of the main loop is bounded by $O(\sqrt{|V|})$. Since each iteration (BFS and DFS phases) takes $O(|E|+|V|)$ time in a sparse graph, the overall runtime of the Hopcroft-Karp algorithm is:

Runtime: $O(\sqrt{|V|}(|E|+|V|))$

In this lecture, we will focus on understanding and proving why the number of iterations is $O(\sqrt{|V|})$.

Proof of $O(\sqrt{|V|})$ Iterations in Hopcroft-Karp Algorithm

To understand why the Hopcroft-Karp algorithm is efficient, we need to prove that the number of iterations in the main loop is indeed bounded by $O(\sqrt{|V|})$. The proof is structured in three parts.

Part 1: Increasing the Length of Shortest Augmenting Paths

Claim: With each iteration of the Hopcroft-Karp algorithm, the length of the shortest augmenting path increases strictly. More specifically, if $k$ is the length of the shortest augmenting path in iteration $i$, then the length of the shortest augmenting path in iteration $i+1$ will be at least $k+2$.

Why $k+2$ and not $k+1$? Augmenting paths in bipartite graphs always have odd length because they alternate between partitions $A$ and $B$ and start and end in different partitions (unmatched vertices are in different partitions in a bipartite graph if a perfect matching is not possible, and if a perfect matching is possible, then no augmenting path exists). Therefore, the length of an augmenting path is always an odd integer. If the shortest augmenting path length is $k$, the next possible length must be at least $k+2$.

Proof of Claim 1:

Let $M$ be the matching at the beginning of iteration $i$, and let $S_i$ be the maximal set of vertex-disjoint shortest $M$-augmenting paths of length $k$. Let $M^{\prime }=M\oplus ({\bigcup }_{P\in S_i}P)$ be the matching after augmentation in iteration $i$. We want to show that any $M^{\prime }$-augmenting path $P^{\prime }$ must have length greater than $k$.

Consider an $M^{\prime }$-augmenting path $P^{\prime }$. We analyze how $P^{\prime }$ can interact with the paths in $S_i$.

Case 1: $P^{\prime }$ is Vertex-Disjoint from All Paths in $S_i$.

If $P^{\prime }$ is vertex-disjoint from all paths in $S_i$, then $P^{\prime }$ was also an $M$-augmenting path in iteration $i$. Since $S_i$ was chosen to be a maximal set of vertex-disjoint shortest $M$-augmenting paths of length $k$, and $P^{\prime }$ is vertex-disjoint from all paths in $S_i$, $P^{\prime }$ cannot be of length $k$. If it were of length $k$, we could have added it to $S_i$, contradicting the maximality of $S_i$. Therefore, in this case, $|P^{\prime }|>k$. Since augmenting path lengths are odd, $|P^{\prime }|\ge k+2$.

Case 2: $P^{\prime }$ Shares Vertices with at Least One Path in $S_i$.

Let $P\in S_i$ be a path that shares at least one vertex with $P^{\prime }$. To analyze this case, we need a helper lemma that relates the lengths of intersecting augmenting paths.

Using the Lemma to Prove Claim:

Let $P\in S_i$ be a path that intersects with $P^{\prime }$. We know $|P|=k$. By the lemma, $|P^{\prime }|\ge |P|+2|P\cap P^{\prime }|$. Since $P$ and $P^{\prime }$ intersect at least at one vertex, $|P\cap P^{\prime }|\ge 1$. Thus, $|P^{\prime }|\ge k+2\cdot 1=k+2$.

Therefore, in both Case 1 and Case 2, any $M^{\prime }$-augmenting path $P^{\prime }$ must have length at least $k+2$. This proves that with each iteration, the length of the shortest augmenting path increases strictly (by at least 2).

Lemma

Let $M$ be a matching, $P$ be a shortest $M$-augmenting path, and $P^{\prime }$ be an $M^{\prime }$-augmenting path where $M^{\prime }=M\oplus P$. Then, if $P$ and $P^{\prime }$ share vertices, $|P^{\prime }|\ge |P|+2|P\cap P^{\prime }|$.

Proof of the Lemma: $|P^{\prime }|\ge |P|+2|P\cap P^{\prime }|$

Let $M^{\prime }=M\oplus P$ and $M^{\prime \prime }=M^{\prime }\oplus P^{\prime }$. Then $M^{\prime \prime }=(M\oplus P)\oplus P^{\prime }=M\oplus (P\oplus P^{\prime })$. The size of the matching increases by 1 with each augmentation. Thus, $|M^{\prime }|=|M|+1$ and $|M^{\prime \prime }|=|M^{\prime }|+1=|M|+2$. This implies that $|M^{\prime \prime }|-|M|=2$.

Consider the symmetric difference $M\oplus M^{\prime \prime }=M\oplus (M\oplus P\oplus P^{\prime })=P\oplus P^{\prime }$. The set of edges $P\oplus P^{\prime }$ consists of paths and cycles where edges alternate between $P$ and $P^{\prime }$. Since $|M^{\prime \prime }|$ is larger than $|M|$ by 2, $P\oplus P^{\prime }$ must contain at least two more edges from $M^{\prime \prime }$ (which are from $P^{\prime }\setminus P$ and $P\setminus P^{\prime }$) than from $M$. This can only happen if $P\oplus P^{\prime }$ contains at least two vertex-disjoint $M$-augmenting paths (or components that act like augmenting paths in terms of edge imbalance). However, a simpler observation is that $|M\oplus M^{\prime \prime }|$ must be related to the increase in matching size, which is 2.

We know that $|P\oplus P^{\prime }|=|P\cup P^{\prime }|-|P\cap P^{\prime }|$. Using the inclusion-exclusion principle, $|P\cup P^{\prime }|=|P|+|P^{\prime }|-|P\cap P^{\prime }|$. Therefore, $|P\oplus P^{\prime }|=(|P|+|P^{\prime }|-|P\cap P^{\prime }|)-|P\cap P^{\prime }|=|P|+|P^{\prime }|-2|P\cap P^{\prime }|$.

It’s argued that $|M\oplus M^{\prime \prime }|=|P\oplus P^{\prime }|\ge 2|P|$. This is because $M^{\prime \prime }$ is obtained from $M$ by two augmentations, and $P$ is a shortest $M$-augmenting path. It implies that the “augmenting components” in $M\oplus M^{\prime \prime }$ must have lengths related to $|P|$. A more direct argument relies on the fact that $|M^{\prime \prime }|-|M|=2$. The symmetric difference $M\oplus M^{\prime \prime }$ essentially represents the changes made to $M$ to get $M^{\prime \prime }$. Since the matching size increased by 2, we expect the total “length” of change to be at least related to twice the shortest augmenting path length. A rigorous justification for $|M\oplus M^{\prime \prime }|\ge 2|P|$ would require a more detailed decomposition of $M\oplus M^{\prime \prime }$ into augmenting paths.

Assuming $|P\oplus P^{\prime }|\ge 2|P|$, we have $|P|+|P^{\prime }|-2|P\cap P^{\prime }|\ge 2|P|$. Rearranging this inequality, we get $|P^{\prime }|\ge |P|+2|P\cap P^{\prime }|$. This proves the lemma.

Part 2: Bounding the Number of Iterations based on Path Length

Claim: Let $M$ be a matching, and let $k$ be the length of a shortest $M$-augmenting path. If $M_{max}$ is a maximum matching, then $|M_{max}|\le |M|+\frac{|V|}{k+1}$.

Proof of Claim:

Assume $|M_{max}|>|M|$. Consider the symmetric difference $M\oplus M_{max}$. As we discussed earlier, $M\oplus M_{max}$ decomposes into vertex-disjoint paths and cycles. Since $|M_{max}|>|M|$, there must be at least $|M_{max}|-|M|$ vertex-disjoint paths in this decomposition that are $M$-augmenting paths. Let $\mathcal{P}$ be a set of vertex-disjoint $M$-augmenting paths from $M\oplus M_{max}$. We can choose $\mathcal{P}$ to be a set of paths such that $|\mathcal{P}|=|M_{max}|-|M|$.

Since $k$ is the length of the shortest $M$-augmenting path, each path in $\mathcal{P}$ must have length at least $k$. Each path of length at least $k$ contains at least $k+1$ vertices. Since the paths in $\mathcal{P}$ are vertex-disjoint, the total number of vertices involved in these paths is at least $(|M_{max}|-|M|)(k+1)$. This number cannot exceed the total number of vertices in the graph, $|V|$.

Therefore, we have: $(|M_{max}|-|M|)(k+1)\le |V|$.

Dividing both sides by $(k+1)$, we get: $|M_{max}|-|M|\le \frac{|V|}{k+1}$.

Rearranging, we obtain: $|M_{max}|\le |M|+\frac{|V|}{k+1}$. This proves Claim 2.

Part 3: Bounding the Total Number of Iterations - $O(\sqrt{|V|})$

We now demonstrate that the Hopcroft-Karp algorithm requires at most $O(\sqrt{|V|})$ iterations to find a maximum matching. We divide the algorithm’s execution into two phases based on the length of the shortest augmenting path, $k$.

A) First Phase: Iterations with Short Augmenting Paths

Consider the initial iterations where the length of the shortest augmenting path, $k$, is less than $\sqrt{|V|}$. We know from Part 1 that in each iteration, the length of the shortest augmenting path strictly increases. Since the shortest augmenting path length is at least 1 and must be less than $\sqrt{|V|}$ in this phase, the number of iterations in this phase is limited.

In the most conservative scenario, the shortest augmenting path length starts at 1 and increases by at least 2 in each iteration. Therefore, the maximum number of iterations before the shortest path length becomes $\ge \sqrt{|V|}$ is roughly $\frac{\sqrt{|V|}}{2}$. Thus, the number of iterations in this first phase is at most $O(\sqrt{|V|})$.

B) Second Phase: Iterations with Long Augmenting Paths

Now consider the iterations where the length of the shortest augmenting path, $k$, is at least $\sqrt{|V|}$, i.e., $k\ge \sqrt{|V|}$. From Part 2, Claim 2, we have the bound:

$|M_{max}|\le |M_{current}|+\frac{|V|}{k+1}$

where $M_{current}$ is the matching at the beginning of the current iteration and $M_{max}$ is a maximum matching. Since we are in the second phase where $k\ge \sqrt{|V|}$, it follows that:

$\frac{|V|}{k+1}\le \frac{|V|}{\sqrt{|V|}+1}<\frac{|V|}{\sqrt{|V|}}=\sqrt{|V|}$

Therefore, for any iteration in this second phase,

$|M_{max}|\le |M_{current}|+\sqrt{|V|}$

This inequality tells us that when we are in the second phase (long augmenting paths), the size of our current matching $M_{current}$ is already within $\sqrt{|V|}$ of the size of a maximum matching $M_{max}$. Since in each iteration, the size of the matching increases by at least 1, there can be at most $\sqrt{|V|}$ remaining iterations to reach a maximum matching from this point.

Total Iterations:

The total number of iterations for the Hopcroft-Karp algorithm is the sum of the iterations in the first phase and the second phase. Both phases are bounded by $O(\sqrt{|V|})$ iterations. Therefore, the total number of iterations is $O(\sqrt{|V|})+O(\sqrt{|V|})=O(\sqrt{|V|})$.

This concludes the proof that the Hopcroft-Karp algorithm finds a maximum matching in $O(\sqrt{|V|})$ iterations, leading to an overall time complexity of $O(\sqrt{|V|}(|E|+|V|))$.

Practical Considerations: Achieving Near-Maximum Matchings

In practice, if achieving a perfectly maximum matching is not strictly necessary, we can consider stopping the Hopcroft-Karp algorithm after a certain number of iterations or when the length of the shortest augmenting path becomes sufficiently large. This can provide a good approximation of a maximum matching with reduced computational effort. For instance, stopping after a fixed number of iterations or when the shortest path length exceeds a threshold can often yield a matching that is very close to maximum size in real-world scenarios.

Conclusion

The Hopcroft-Karp algorithm is guaranteed to find a maximum matching in a bipartite graph in $O(\sqrt{|V|})$ iterations. Since each iteration (BFS and DFS phases) takes linear time $O(|E|+|V|)$, the overall time complexity is $O(\sqrt{|V|}(|E|+|V|))$.

This concludes the proof that the Hopcroft-Karp algorithm is indeed very efficient for finding maximum matchings in bipartite graphs, with a runtime significantly better than the simpler augmenting path algorithms.

Overview of Matching Algorithms (Beyond Bipartite)

As we discussed matching algorithms in the context of Christofides’ algorithm (finding a minimum weight perfect matching), let’s briefly mention the complexity landscape for matching problems in general graphs (beyond bipartite graphs).

For bipartite graphs:

• Hopcroft-Karp Algorithm (Unweighted): Achieves a time complexity of $O(|V{|}^{1/2}\cdot |E|)$.
• More Advanced Algorithms (Weighted): Algorithms exist with complexities close to $O(|E{|}^{1+o(1)})$ for weighted bipartite matching, especially with polynomially bounded weights.

For general graphs (non-bipartite):

• Micali-Vazirani Algorithm (Unweighted): A complex algorithm that achieves a time complexity of $O(|V{|}^{1/2}\cdot |E|)$, similar to Hopcroft-Karp for bipartite graphs. Gabow-Tarjan algorithm is another algorithm with similar complexity.
• Matrix Multiplication Based Algorithms (Unweighted): Algorithms using fast matrix multiplication have achieved slightly better theoretical complexities like $O(|V{|}^{2.373})$ for unweighted maximum matching.
• Gabow’s Algorithms (Weighted): For weighted matching in general graphs, algorithms like Gabow’s algorithms exist, with complexities around $O(|V{|}^3)$ for finding maximum weight or minimum weight perfect matchings.

Finding minimum weight perfect matchings, as required in Christofides’ Algorithm, can be solved in polynomial time, although the algorithms are more involved than MST algorithms.

Metric TSP and Approximation Algorithms

In our previous lecture, we discussed the Traveling Salesperson Problem (TSP), a classic NP-complete problem. We highlighted that while finding an optimal solution for the general TSP is computationally intractable, the Metric TSP, a special case where distances satisfy the triangle inequality, admits efficient approximation algorithms.

We explored a 2-approximation algorithm for the Metric TSP based on Minimum Spanning Trees (MST). While a 2-approximation is valuable, we aim for even better solutions. Today, we will delve into Christofides’ Algorithm, a significant advancement that provides a 1.5-approximation for the Metric TSP, a long-standing benchmark in this area.

Christofides Algorithm: Achieving a 1.5-Approximation

Christofides’ Algorithm, developed by Nicos Christofides in 1976, is a polynomial-time algorithm that guarantees a tour with a length at most 1.5 times the optimal tour length for the Metric TSP. It elegantly combines the concept of Minimum Spanning Trees (MSTs) with perfect matchings to achieve this improved approximation ratio.

Steps of Christofides Algorithm

Let $G=(V,E)$ be a complete graph with vertices representing cities and edge weights $l(u,v)$ representing distances satisfying the triangle inequality. Christofides’ Algorithm proceeds in the following steps:

1. Compute a Minimum Spanning Tree (MST) $T$ of $G$.

   • We begin by finding a Minimum Spanning Tree $T$ of the complete graph $G$. Algorithms like Kruskal’s or Prim’s can efficiently compute an MST in polynomial time, typically $O(|E|\log |V|)$ or $O(|V{|}^2)$.
   • Key Insight: The total weight of the MST, $l(T)$, serves as a lower bound for the optimal TSP tour length, $opt(K_n,l)$. This is because any TSP tour must span all vertices, and an MST is the minimum weight spanning subgraph. Hence, $l(T)\le opt(K_n,l)$.

2. Identify Vertices with Odd Degree in $T$.

   • Let $X$ be the set of vertices in the MST $T$ that have an odd degree.
   • Property of Graph Degrees: In any graph, the number of vertices with odd degree is always even. Therefore, $|X|$ is even.

3. Find a Minimum Weight Perfect Matching $M$ in the subgraph induced by $X$.

   • Consider the subgraph of $G$ induced by the vertices in $X$. Let’s call this subgraph $G[X]$.
   • Find a minimum weight perfect matching $M$ in $G[X]$. Since $|X|$ is even, a perfect matching exists if $G[X]$ is complete (which it is since $G$ is complete). Efficient algorithms exist to find minimum weight perfect matchings in polynomial time, although they are more complex than MST algorithms.
   • Key Insight: We are focusing on the vertices with odd degrees in the MST. By adding a perfect matching of these vertices, we aim to make all vertex degrees even, paving the way for an Eulerian tour construction.

4. Construct a Multigraph $H=T\cup M$.

   • Create a multigraph $H$ by taking the union of the edges of the MST $T$ and the edges of the minimum weight perfect matching $M$. Note that $H$ might be a multigraph because $T$ and $M$ could share vertices, and thus $H$ might contain multiple edges between the same pair of vertices.
   • Degree Parity in $H$: In $H$, every vertex has an even degree. Why? Consider any vertex $v$. If $v\notin X$, it had an even degree in $T$. Since $M$ only involves vertices in $X$, the degree of $v$ remains even in $H$. If $v\in X$, it had an odd degree in $T$. Since $M$ is a perfect matching on $X$, exactly one edge of $M$ is incident to $v$. Adding this edge to $H$ makes the degree of $v$ even (odd + 1 = even).

5. Find an Eulerian Tour $W$ in $H$.

   • Since every vertex in $H$ has an even degree and $H$ is connected (because $T$ is spanning), $H$ contains an Eulerian tour $W$. We can find such a tour efficiently using Hierholzer’s algorithm.
   • Eulerian Tour Properties: The Eulerian tour $W$ traverses every edge of $H$ exactly once.

6. Convert Eulerian Tour to Hamiltonian Cycle $C$ by Shortcutting.

   • Traverse the Eulerian tour $W$. As we traverse, create a Hamiltonian cycle $C$ by “shortcutting” repeated vertices. Whenever we are about to visit a vertex $v$ that has already been visited in $C$, we skip to the next unvisited vertex in $W$.
   • Triangle Inequality Guarantee: Due to the triangle inequality, shortcutting does not increase the tour length. By skipping repeated vertices, we create a valid Hamiltonian cycle $C$ (visiting each vertex exactly once).

The resulting cycle $C$ is the tour produced by Christofides’ Algorithm.

Justification and Intuition Behind Christofides Algorithm

Christofides’ Algorithm builds upon the 2-approximation MST algorithm by strategically adding a minimum weight perfect matching to the MST. Let’s understand the rationale behind each step:

• MST as a Backbone: The MST provides a low-cost backbone connecting all cities. Its weight is a lower bound on the optimal TSP tour. However, simply traversing the MST (like in the 2-approximation algorithm by doubling edges) leads to revisiting vertices.

• Addressing Odd-Degree Vertices: The problem with the doubled MST approach is that it forces us to revisit vertices to create a closed tour. Christofides’ Algorithm cleverly addresses this by focusing on the odd-degree vertices in the MST. These vertices are the “problem points” hindering the direct construction of an Eulerian tour from the MST itself.

• Minimum Weight Perfect Matching: By finding a minimum weight perfect matching $M$ of the odd-degree vertices $X$, we are essentially “repairing” the MST to make all degrees even. We choose a minimum weight matching to keep the added cost as low as possible. The edges in $M$ can be thought of as “shortcuts” that efficiently connect the odd-degree vertices in pairs, making their degrees even without adding too much extra length.

• Eulerian Tour and Shortcutting: After adding the matching $M$ to the MST $T$, we obtain a multigraph $H$ where all vertices have even degrees. This guarantees the existence of an Eulerian tour. By shortcutting this Eulerian tour, we transform it into a Hamiltonian cycle, ensuring each city is visited exactly once, while leveraging the low cost structure built upon the MST and the matching.

Approximation Ratio Proof: Why 1.5-Approximation?

The crucial aspect of Christofides’ Algorithm is that it achieves a 1.5-approximation ratio. Let’s outline the proof to understand why the length of the tour $C$ produced by Christofides’ Algorithm is guaranteed to be no more than 1.5 times the optimal TSP tour length, $opt(K_n,l)$.

1. MST Lower Bound: We know that the weight of the MST, $l(T)$, is a lower bound on the optimal TSP tour length: $l(T)\le opt(K_n,l)$

2. Bounding the Minimum Weight Perfect Matching $M$: Consider an optimal TSP tour, $C_{opt}$. Let $X$ be the set of odd-degree vertices in $T$. Consider the vertices in $X$ as they appear in $C_{opt}$. Traverse the optimal tour $C_{opt}$. As we encounter vertices from $X$, we are effectively visiting them in some order. Let’s create two perfect matchings on $X$ by considering alternating edges of the optimal tour as we visit vertices in $X$.

   • Imagine traversing $C_{opt}$ and encountering vertices of $X$ in order $x_1,x_2,x_3,x_4,...,x_{2k}$ (since $|X|=2k$ is even).
   • Consider two sets of edges from $C_{opt}$ connecting vertices in $X$:
     • $M_1=\{\{x_1,x_2\},\{x_3,x_4\},...,\{x_{2k-1},x_{2k}\}\}$
     • $M_2=\{\{x_2,x_3\},\{x_4,x_5\},...,\{x_{2k},x_1\}\}$ (wrap around)

   Both $M_1$ and $M_2$ are perfect matchings on $X$. Because of the triangle inequality, the sum of the weights of edges in $M_1$ is no more than the weight of the path segments in $C_{opt}$ connecting these pairs. Similarly for $M_2$. Importantly, the edges of $M_1$ and $M_2$, when considered as paths in $C_{opt}$, are edge-disjoint and together they form an alternating cycle cover of the vertices in $X$ within $C_{opt}$.

   Therefore, $l(M_1)+l(M_2)\le l(C_{opt})=opt(K_n,l)$. Since $M$ is a minimum weight perfect matching on $X$, its weight must be less than or equal to the weight of either $M_1$ or $M_2$ (at least one of which must have weight no more than half of $l(C_{opt})$). Thus, $l(M)\le \min (l(M_1),l(M_2))\le \frac{1}{2}(l(M_1)+l(M_2))\le \frac{1}{2}opt(K_n,l)$.

   Hence, we have the bound: $l(M)\le \frac{1}{2}opt(K_n,l)$

3. Length of Eulerian Tour $W$: The multigraph $H$ is formed by $T\cup M$. The length of the Eulerian tour $W$ in $H$ is the sum of the weights of edges in $T$ and $M$: $l(W)=l(T)+l(M)$

4. Approximation Ratio: Combining the bounds for $l(T)$ and $l(M)$: $l(W)=l(T)+l(M)\le opt(K_n,l)+\frac{1}{2}opt(K_n,l)=\frac{3}{2}opt(K_n,l)$

5. Hamiltonian Cycle $C$ via Shortcutting: Since shortcutting does not increase the length (due to triangle inequality), the length of the Hamiltonian cycle $C$ obtained by shortcutting $W$ is no longer than $l(W)$: $l(C)\le l(W)$

Combining all inequalities, we have: $l(C)\le l(W)\le \frac{3}{2}opt(K_n,l)$

This proves that Christofides’ Algorithm provides a 1.5-approximation for the Metric TSP.

Recent Advances and Limits of Approximation

For decades, Christofides’ Algorithm remained the best known polynomial-time approximation algorithm for the Metric TSP. It was a major open question whether a better approximation ratio could be achieved.

• Long-Standing Open Problem: For a long time, achieving an approximation ratio better than 1.5 for the Metric TSP was a significant challenge.

• Breakthrough in 2020: In September 2020, a breakthrough was achieved by Karlin, Klein, and Gharan. They presented a polynomial-time algorithm with an approximation ratio of $(3/2-10^{-36})$. This is a very slight improvement over 1.5, but it was a major theoretical advancement, breaking the 1.5 barrier for the first time in polynomial time.

• Current Research: Research continues to explore whether even better approximation ratios are possible. However, there are also limitations.

• NP-Hardness of Better Approximation: It is known that it is NP-hard to achieve an approximation ratio better than 1.008 for the Metric TSP. This means that we cannot expect to find polynomial-time algorithms that get arbitrarily close to the optimal solution unless P=NP.

Therefore, while Christofides’ Algorithm is not optimal, it provides a practically useful and theoretically significant approximation guarantee for the Metric TSP, and further substantial improvements are likely to be very challenging to achieve due to complexity-theoretic barriers.

Continue here: 07 Graph Coloring, Greedy Coloring, Smallest-Last Heuristics, Block Graph Colorings