Hopcroft–Karp algorithm

The Hopcroft–Karp algorithm finds maximum cardinality matchings in bipartite graphs in ${\displaystyle O({\sqrt {V}}E)}$ time, where V is the number of vertices and E is the number of edges of the graph.^[1] In the worst case of dense graphs, i.e., when ${\displaystyle E=O(V^{2})}$, the worst-case time estimate is ${\displaystyle O(V^{5/2})}$.

The algorithm is an adaptation of the Edmonds-Karp algorithm for maximum flow, since bipartite matching is equivalent to finding the maximum (integer) flow if the vertices in each partition are considered sources (respectively sinks) of capacity 1. The minimal cut associated with the flow is equivalent to the minimal vertex cover associated with the matching.

Instead of finding just a single augmenting path, the algorithm finds a maximal set of shortestest paths in each iteration ^[2]. As a result only ${\displaystyle O({\sqrt {V}})}$ iterations are needed.

References

1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. Introduction to Algorithms (2nd edition ed.). MIT Press and McGraw-Hill. pp. 696–697. ISBN 0-262-03293-7. {{cite book}}: |edition= has extra text (help)
2. Norbert Blum (1999). "A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs".