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] [2]} 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 shortest paths in each iteration ^[3]. As a result only ${\displaystyle O({\sqrt {V}})}$ iterations are needed.

Definition

Consider a graph G(V,E). The following definitions are relative to a matching M in G.

• An alternating path is a path in which the edges would belong alternatively to M and E-M.
• A free vertex is a vertex which has no incoming edges which belong to M.
• Finally, an augmenting path P is an alternating path such that both its end points are free vertices.
• Symmetric difference ${\displaystyle M'=M\oplus P}$  has all edges of M and P except shared edges ${\displaystyle M\cap P}$ 

Algorithm

The basic concept that the algorithm relies on is that if M is a matching of size n, and P is an augmenting path relative to M, then the matching M ⊕ P would have a size of n + 1. Thus, since there would be no matching greater in size than the maximum matching, the maximum matching would not have an augmenting path.

Let U and V be the two sets in the bipartition of G, and let the matching from U to V at any time be represented as the set M.

The algorithm is run in phases. Each phase consists of the following steps.

• A breadth first search is run from the free vertices in U. This search stops at the first layer k where one or more free vertices in V are reached. Collect all free vertices in V at layer k and put them in the set F. That is, a vertex v is put into F if and only if it ends a shortest augmenting path.
• Find a maximal set of vertex disjoint augmenting paths of length k. This is set may be computed by depth first search from F to the free vertices in U, using the breadth first layering to guide the search: the depth first search is only allowed to follow edges that lead to an unused vertex in the previous layer. Once an augmenting path is found that involves one of the vertices in F, the depth first search is continued from the next starting vertex.
• Every one of the paths found in this way is used to enlarge M.

The algorithm terminates when no more augmenting paths are found in the breadth first search part of one of the phases.

Analysis

Each phase consists of a single breadth first search and a single depth first search. Thus, a single phase may be implemented in linear time. Therefore, the first √n phases, in a graph with n vertices and m edges, take time O(m √n).

It can be shown that each phase increases the length of the shortest augmenting path by at least one: the phase finds a maximal set of augmenting paths of the given length, so any remaining augmenting path must be longer. Therefore, once the initial √n phases of the algorithm are complete, the shortest remaining augmenting path has at least √n edges in it. However, the symmetric difference of the eventual optimal matching and of the partial matching M found by the initial phases forms a collection of vertex-disjoint augmenting paths and alternating cycles. If each of the paths in this collection has length at least √n, there can be at most √n paths in the collection, and the size of the optimal matching can differ from the size of M by at most √n edges. Since each phase of the algorithm increases the size of the matching by at least one, there can be at most √n additional phases before the algorithm terminates.

Since the algorithm performs a total of at most 2√n phases, it takes a total time of O(m √n).

References

1. John E. Hopcroft, Richard M. Karp: An ${\displaystyle n^{5/2}}$  Algorithm for Maximum Matchings in Bipartite Graphs. SIAM J. Comput. 2(4), 225-231 (1973)
2. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. "26.5: The relabel-to-front algorithm". Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. pp. pp. 696–697. ISBN 0-262-03293-7. {{cite book}}: |pages= has extra text (help)
3. Norbert Blum (1999). "A Simplified Realization of the Hopcroft-Karp Approach to Maximum Matching in Nonbipartite Graphs".