Sign in to watch this lesson
Advanced - Graphs · 5:21
Kuhn's Algorithm: Maximum Bipartite Matching
A matching in a bipartite graph grows by one whenever we flip an augmenting path, an alternating path whose two ends are free, and Berge's lemma says a matching with no augmenting path is maximum. Kuhn's algorithm runs one depth-first search per left vertex, clearing the visited array each time, for O(n₁·m) in total, so the smaller side belongs on the left. König's theorem then turns the maximum matching into a minimum vertex cover, which solves problems such as covering every flagged cell of a grid with the fewest rows and columns.
You will learn
- Define a matching, saturated and free vertices, alternating and augmenting paths, and explain why flipping an augmenting path adds one edge
- Implement Kuhn's algorithm (try_kuhn with used[] over left vertices and mt[] over right vertices), reset used once per left vertex, and analyse it as O(n₁·m)
- Explain Berge's lemma through the symmetric difference of two matchings (alternating paths and even cycles)
- Apply König's theorem: minimum vertex cover = maximum matching, maximum independent set = n − maximum matching, and build the cover from the final search