Bipartite matching
A bipartite graph splits nodes into two sides with edges only crossing between them. A matching picks edges so no node is used twice, and we want the largest matching. A simple approach finds one augmenting path at a time, but that can be slow.
Augmenting paths in matching
An augmenting path starts and ends at unmatched nodes and alternates between unused and used edges. Flipping the edges along it grows the matching by one. The trick to going faster is to find many such paths together.
The two phase loop
Hopcroft Karp alternates two phases:
- A breadth first search labels nodes by distance and finds the length of the shortest augmenting paths.
- A depth first search then greedily flips a maximal set of shortest augmenting paths at once.
Each round increases the shortest path length, so only a small number of rounds are needed. Processing many disjoint paths per round is what makes it faster than one at a time matching on large graphs.
Key idea
Alternate a breadth first search that finds shortest augmenting paths with a depth first phase that flips many of them at once.