Bipartite Matching Algorithms — Hopcroft-Karp, Gale-Shapley & Hungarian Method | Chapter 25 in Introduction to Algorithms

Chapter 25 of Introduction to Algorithms (CLRS) presents a rich collection of algorithms for solving matching problems in bipartite graphs. These problems involve pairing elements from two disjoint sets—such as jobs and workers or students and schools—based on constraints like maximum size, stability, or optimal assignment weights. This chapter explores the powerful Hopcroft-Karp algorithm for maximum matching, the Gale-Shapley algorithm for stable marriage problems, and the Hungarian algorithm for solving the assignment problem with weights.

📺 Watch the full podcast-style summary above, or continue reading for a complete breakdown of the key matching strategies, theorems, and complexity results introduced in Chapter 25.

Maximum Bipartite Matching

A matching is a set of edges with no shared vertices. In bipartite graphs, the goal is often to find the maximum matching, or the largest possible set of such non-overlapping pairs.

• M-Alternating Path: Path that alternates between matching and non-matching edges.
• M-Augmenting Path: Alternating path that begins and ends at unmatched vertices; its symmetric difference with M yields a larger matching.
• Key result: No M-augmenting path ⇨ matching is maximum.

Hopcroft-Karp Algorithm

The Hopcroft-Karp algorithm finds a maximum matching in bipartite graphs in O(√V × E) time—significantly faster than using augmenting paths individually.

• BFS Phase: Constructs layers of shortest augmenting paths.
• DFS Phase: Finds a maximal set of vertex-disjoint augmenting paths.
• Augmentation: Performed in phases until no augmenting paths remain.

Key lemmas (25.5 to 25.7) support the algorithm's correctness, leading to Theorem 25.8 that guarantees both optimality and runtime.

The Stable Marriage Problem

The Stable Marriage Problem seeks a matching where no unmatched pair would prefer each other over their current partners—a property known as stability.

• Input: Each person ranks all members of the opposite set.
• Blocking Pair: An unmatched pair who both prefer each other over their matches.
• Gale-Shapley Algorithm:
  • Women propose in order of preference.
  • Men accept the best offer so far and may later switch.
  • Rejected women continue proposing.
• Time Complexity: O(n²)
• Key Theorems:
  • 25.9: Guarantees termination with a stable matching.
  • 25.11: Matching is optimal for proposers.
  • 25.13: Worst for the other side (proposee).

Hungarian Algorithm – The Assignment Problem

The Hungarian algorithm solves the assignment problem—finding a perfect matching in a weighted bipartite graph that maximizes (or minimizes) total weight.

• Input: Bipartite graph with weights and equal-sized partitions.
• Feasible Vertex Labeling: Assign labels to ensure l(h) + r(h) ≤ w(l, r).
• Equality Subgraph (G_h): Contains edges where label-sum equals weight.
• Perfect Matching: Exists in G_h → solution is optimal (Theorem 25.14).

Steps of the Hungarian Algorithm:

1. Start with feasible labels and an empty matching.
2. Use BFS to search for M-augmenting paths.
3. If none found, update labels to reduce slack and add tight edges to G_h.
4. Repeat until a perfect matching is found.

• Time Complexity: O(n⁴); faster implementations achieve O(n³).
• Lemma 25.15: Ensures each labeling step preserves feasibility.

Glossary of Key Terms

• Matching: Set of non-overlapping edges in a graph.
• Bipartite Graph: Graph where vertices are divided into two disjoint sets.
• M-Alternating Path: Alternates between matched and unmatched edges.
• M-Augmenting Path: Increases the size of a matching.
• Stable Matching: No pair prefers each other over their matches.
• Blocking Pair: Violates stability due to mutual preference.
• Gale-Shapley Algorithm: Stable matching algorithm based on proposals.
• Feasible Labeling: Label sum is less than or equal to edge weight.
• Equality Subgraph: Edges tight under labeling constraint.
• Perfect Matching: Covers every vertex in both partitions.
• Assignment Problem: Find the best perfect matching in a weighted graph.

Conclusion

Chapter 25 unpacks the theory and practice behind bipartite matching problems in a variety of forms—whether the goal is size, stability, or weight. From the highly efficient Hopcroft-Karp algorithm to the real-world relevance of the Gale-Shapley and Hungarian methods, this chapter brings together combinatorics, optimization, and algorithmic design in one of the most fascinating domains in graph theory.

🎓 Watch the full breakdown on YouTube: Algorithms for Matching in Bipartite Graphs — CLRS Chapter 25.

📘 Want more CLRS content? Visit the Last Minute Lecture YouTube channel for chapter-by-chapter academic summaries.

If you found this breakdown helpful, be sure to subscribe to Last Minute Lecture for more chapter-by-chapter textbook summaries and academic study guides.