The Hungarian Algorithm for Maximum Bipartite Matching
What you'll learn: How to systematically find the largest possible matching in a bipartite graph by iteratively discovering augmenting paths.
The Core Idea
The Hungarian Algorithm solves the maximum bipartite matching problem by repeatedly finding augmenting paths (paths that start and end at unmatched vertices, alternating between edges not in the matching and edges in the matching). Each time you find such a path, you can increase your matching size by one—flip the matched/unmatched status of edges along the path.
The algorithm continues until no more augmenting paths exist. By Berge's Theorem (which you've already learned), a matching is maximum if and only if there are no augmenting paths, so when the algorithm stops, you've found a maximum matching.
How It Works
- Start with any matching (even the empty matching works)
- Search for an augmenting path starting from any unmatched vertex in one partition
- If found: "Augment" the matching by flipping edge statuses along the path (add unmatched edges, remove matched ones). This increases matching size by 1
- Repeat steps 2-3 until no augmenting paths remain
- Done: Your current matching is maximum
Think of it like upgrading a network of connections: you keep finding opportunities to add one more connection by rearranging existing ones, until no further improvements are possible.
The algorithm typically uses BFS or DFS to search for augmenting paths efficiently, exploring alternating matched/unmatched edges from unmatched vertices.
Key Takeaway: The Hungarian Algorithm finds maximum matchings in bipartite graphs by repeatedly discovering and applying augmenting paths until none remain, guaranteeing optimality by Berge's Theorem.