Hopcroft–Karp algorithm

The Hopcroft–Karp algorithm finds maximum cardinality matchings in bipartite graphs in ${\displaystyle O({\sqrt {V}}E)}$ time (another estimation is O(V ^5/2) ^[1]). It 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.

Algorithm

Input: Bipartite graph ${\displaystyle G(V=L\cup R,E)}$ 

Output: Matching ${\displaystyle M\subseteq E}$ 

${\displaystyle M\leftarrow \emptyset }$ 

repeat

${\displaystyle {\mathcal {P}}\leftarrow \{P_{1},P_{2},\dots ,P_{k}\}}$  maximal set of vertex-disjoint shortest augmenting paths

${\displaystyle M\leftarrow M\oplus (P_{1}\cup P_{2}\cup \dots \cup P_{k})}$ 

until ${\displaystyle {\mathcal {P}}=\emptyset }$ 

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2001) [1990]. "26". 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)

1. Lipski W., Kombinatoryka dla Programistow, [Combinatorics for Programmers], Wydawnictwa Naukowo-Techniczne, Warzawa, 1982.