Hopcroft-Karp and the Faster Algorithm for Bipartite Matching
Hopcroft and Karp accelerated bipartite matching by finding many shortest augmenting paths in each phase instead of one path at a time, achieving O(E√V) time.
Bipartite matching turns pairing constraints into a graph problem
A bipartite graph divides vertices into two sides and allows edges only across the division. A matching selects edges that share no endpoints, representing compatible pairs such as workers and jobs, students and projects, or machines and tasks. NIST defines bipartite matching as finding such pairings, with maximum matching seeking the largest possible set.[1] A basic augmenting-path algorithm can solve the problem correctly, but if it finds only one new match per graph search, large instances can require many expensive passes.
Maximum matching is not the same as greedy pairing
Choosing an arbitrary available pair can block two later pairs. Correct algorithms need a mechanism for rearranging earlier choices when a better global combination appears.
Augmenting paths provide the mechanism for rearranging a matching
An augmenting path begins and ends at unmatched vertices and alternates between edges outside and inside the current matching. Flipping matched and unmatched status along such a path increases the matching size by exactly one. Hopcroft and Karp’s 1973 paper built on this established characterization and cited earlier matching theory such as Berge’s work.[2] The simple algorithmic approach is therefore clear: keep finding augmenting paths until none remain. The challenge is reducing how many full searches are needed.
Hopcroft and Karp replaced one augmentation with a whole phase of them
Their 1973 SIAM paper presented an algorithm running in O((m+n)√n) steps for a graph with n vertices and m edges.[2] The central improvement was to find a maximal collection of vertex-disjoint shortest augmenting paths during one phase rather than stopping after the first path. Because the paths do not share vertices, their flips do not interfere. One expensive exploration of the graph can therefore increase the matching by many edges at once.
Batching amortizes the cost of discovery
The algorithm pays to construct a global view of the shortest augmenting opportunities, then exploits as many of those opportunities as possible before rebuilding that view.
Breadth-first search organizes the graph into alternating layers
Cornell’s modern Hopcroft-Karp notes define BFS layers beginning from all currently free vertices on one side and traversing alternating unmatched and matched edges.[3] The layering identifies the length of the shortest possible augmenting paths and restricts the next search to edges that advance through those layers. This prevents the algorithm from wasting work on longer augmenting paths while shorter ones remain available.
Depth-first search extracts a maximal set of shortest paths from the layers
After BFS builds the layered graph, depth-first searches look for vertex-disjoint augmenting paths that respect the layer structure. The Technical University of Munich’s algorithm visualization explains this two-stage pattern: BFS discovers the shortest free-to-free distance, and DFS follows compatible layered routes to assemble a maximal collection of augmenting paths.[4] Once those paths are flipped, every shortest augmenting path of the old length has been eliminated.
The layered graph is temporary algorithmic infrastructure
It is not part of the input or final matching. It exists only to coordinate many local path discoveries into one globally efficient phase.
Shortest augmenting paths get longer from phase to phase
The performance proof depends on progress measured not only by matching size but by augmenting-path length. After a phase exhausts a maximal set of shortest augmenting paths, any remaining augmenting path must be longer. Cornell’s notes use this structure in the analysis of the algorithm.[3] The proof then combines two regimes: there cannot be too many phases while shortest paths are short, and once they are long, only a limited number of unmatched pairs can remain. This yields the characteristic square-root bound on phases.
The result improved on repeated one-path augmentation without changing the underlying theorem
Hopcroft-Karp did not discover a new definition of matching. Its contribution was algorithmic organization. The same augmenting-path principle remains the correctness foundation, but the searches are scheduled more intelligently. Dalhousie’s algorithms text notes the parallel with Dinic-style flow algorithms: build a level graph and push a blocking collection of augmentations so the shortest path length increases between iterations.[5] This is a recurring pattern in algorithm design—speed comes from batching compatible improvements, not necessarily from changing the local improvement rule.
Algorithmic speedups often come from changing granularity
Doing more work per phase can reduce total work if that phase eliminates an entire class of future searches.
Why Hopcroft-Karp belongs in the history of algorithms
Hopcroft-Karp belongs in algorithmic history because it transformed a straightforward augmenting-path method into a substantially faster graph algorithm through layering and batching. The original paper’s O((m+n)√n) bound established a new standard for maximum bipartite matching.[2]
The algorithm also illustrates the importance of separating correctness from efficiency. Berge-style augmenting paths explain why the final matching is maximum; Hopcroft and Karp’s phased strategy explains why the algorithm reaches that state quickly. These are different proof obligations and can be improved independently.
That design pattern remains influential. Modern graph algorithms repeatedly build temporary level structures, discover many disjoint improvements and postpone recomputation until a whole frontier has been exhausted. Hopcroft-Karp made that strategy canonical in matching and showed how a careful global schedule can accelerate a simple local operation.
Works Cited
- 01NIST DADS — Bipartite Matching nist.gov
- 02
- 03Cornell CS 6820 — Hopcroft-Karp Algorithm Notes cs.cornell.edu
- 04Technical University of Munich — The Hopcroft-Karp Algorithm algorithms.discrete.ma.tum.de
- 05Dalhousie Algorithms II — The Hopcroft-Karp Algorithm web.cs.dal.ca
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead