Hopcroft–Karp Algorithm

Hopcroft–Karp algorithm is a combinatorial graph algorithm in computation and algorithms that takes an unweighted bipartite graph G = (U ∪ W, E) as input and constructs a maximum-cardinality matching—a largest possible subset of edges M ⊆ E in which no two edges share a common vertex—in O(E √V) worst-case time, where V = |U ∪ W| and E = |E|. Published in 1973 by John E. Hopcroft and Richard M. Karp, the algorithm improved upon the classical O(V E) augmenting-path method derived from the Ford–Fulkerson algorithm and Kőnig's theorem.

Like Dinic's algorithm for network flows (which achieves the same O(E √V) bound when specialized to unit-capacity bipartite networks) and the Micali–Vazirani refinement of the blossom algorithm for general non-bipartite graphs, the Hopcroft–Karp algorithm operates in phases. Each phase uses Breadth-First Search (BFS) to identify the length l of the shortest augmenting paths available with respect to the current matching M, followed by Depth-First Search (DFS) to find a maximal set of vertex-disjoint augmenting paths of length l and augment M along all of them simultaneously. Hopcroft and Karp proved that each phase increases the shortest augmenting path length l by at least 2, bounding the total number of phases by at most 2√V + 2.

Alternating and Augmenting Paths in Bipartite Graphs

Let G = (U ∪ W, E) be an undirected bipartite graph in which every edge e = {u, w} ∈ E connects a left vertex u ∈ U to a right vertex w ∈ W. Given a matching M ⊆ E:

• Edges in M are called matched edges, and edges in E \ M are called free (unmatched) edges.
• A vertex v ∈ U ∪ W incident to an edge in M is matched; otherwise, v is free (exposed).
• An alternating path with respect to M is a simple path in G whose edges alternate between free edges in E \ M and matched edges in M.
• An augmenting path P is an alternating path that begins at a free vertex in U and ends at a free vertex in W. Because it starts and ends with edges in E \ M, an augmenting path always has odd edge length l = 2k + 1, containing k + 1 edges in E \ M and k edges in M.

Taking the symmetric difference of M and P, denoted M ⊕ P = (M \ P) ∪ (P \ M), swaps the status of all edges along P, yielding a valid new matching of cardinality |M ⊕ P| = |M| + 1. More generally, if {P₁, P₂, …, P_r} is a collection of vertex-disjoint augmenting paths for M, then M′ = M ⊕ P₁ ⊕ P₂ ⊕ … ⊕ P_r is a valid matching of size |M′| = |M| + r.

Berge's Theorem and Symmetric Difference Decomposition

By Berge's Lemma (1957), a matching M is of maximum cardinality if and only if G contains no M-augmenting path. To bound how many phases of shortest-path augmentations are needed, Hopcroft and Karp analyzed the symmetric difference M* ⊕ M between any maximum matching M* and the current matching M:

• Every vertex in G has degree at most 2 in the subgraph (U ∪ W, M* ⊕ M) (at most one edge from M and at most one from M*).
• Consequently, M* ⊕ M decomposes into a collection of vertex-disjoint alternating cycles (each of even length, containing an equal number of edges from M and M*) and vertex-disjoint alternating paths.
• If |M*| − |M| = k > 0, then M* ⊕ M must contain at least k vertex-disjoint M-augmenting paths.

Suppose the shortest M-augmenting path in G has length l ≥ 1. Since the k vertex-disjoint M-augmenting paths inside M* ⊕ M each contain at least l edges (and thus at least (l + 1)/2 vertices from U and (l + 1)/2 vertices from W), the sum of their lengths is bounded by the total number of vertices V:

Dual-Stage BFS Layering and DFS Augmentation

Each phase of the Hopcroft–Karp algorithm executes two linear-time O(E) graph traversals:

1. BFS Level-DAG Construction: Enqueue all free vertices u ∈ U at distance layer d[u] = 0. Perform a Breadth-First Search that traverses free edges (E \ M) from U to W and matched edges (M) from W back to U, assigning layer distances d[v] = d[u] + 1. Stop expanding further layers as soon as the first layer containing at least one free vertex in W is completed at odd distance l. If no free vertex in W is reached, M is maximum and the algorithm halts.
2. DFS Maximal Vertex-Disjoint Path Extraction: For each free vertex u ∈ U at layer 0, launch a Depth-First Search restricted to edges advancing by unit layer (d[y] = d[x] + 1) to locate an augmenting path of length l ending at an unvisited free vertex w ∈ W at layer l. Whenever such a path P is found, flip the matching status of its edges (M ← M ⊕ P) and mark all vertices along P (as well as any dead-end vertices explored during DFS) as visited and deleted for the remainder of the phase.

Because every vertex and edge is explored at most a constant number of times by the BFS and the pruning DFS, each phase runs in O(V + E) = O(E) time.

Proof of the 2√V Phase Bound

Within computational complexity theory, the efficiency of the Hopcroft–Karp algorithm follows from two lemmas established in the 1973 paper:

1. Strict Increase of Shortest Path Length: If M′ = M ⊕ P₁ ⊕ … ⊕ P_r is obtained by augmenting along a maximal set of vertex-disjoint shortest M-augmenting paths of odd length l, then every M′-augmenting path in G has length at least l + 2.
2. Square-Root Phase Bound: Consider the execution after √V phases. Since l begins at 1 and increases by at least 2 in each phase, after √V phases the shortest augmenting path has length l ≥ 2⌊√V⌋ + 1 > √V. By the symmetric-difference inequality k = |M*| − |M| ≤ V / (l + 1), at most k ≤ √V additional augmentations can ever occur before M reaches maximum cardinality |M*|. Since each subsequent phase increases |M| by at least 1, at most √V additional phases can execute.

Summing the first √V phases and the at most √V remaining phases yields at most 2√V phases in total, establishing the worst-case time complexity O(E √V). For dense bipartite graphs (E = Θ(V²)), this equals O(V^2.5); for sparse graphs (E = Θ(V)), it equals O(V^1.5).

Comparative Complexity of Bipartite and General Matching Algorithms

1. Dulmage–Mendelsohn Decomposition and Sparse Linear Solvers: Numerical linear algebra packages (LAPACK, SuiteSparse) apply the Hopcroft–Karp algorithm to compute maximum transversal matchings in sparse Jacobian matrices, permuting non-zero entries onto the main diagonal and decomposing differential-algebraic equation (DAE) systems into block-triangular form.
2. Minimum Vertex Cover and Maximum Independent Set (Kőnig's Theorem): Once the Hopcroft–Karp algorithm terminates with maximum matching M, the final BFS reachability layers immediately yield a minimum vertex cover (U \ Z) ∪ (W ∩ Z) (where Z is the set of vertices reachable from free vertices in U via alternating paths) and its complement, a maximum independent set, in O(E) additional time.
3. Comparative Genomics and Orthology Assignment: In computational biology, reciprocal-best-hit and syntenic gene-family graphs between two species are modeled as bipartite graphs in which Hopcroft–Karp identifies maximum one-to-one orthologous gene pairings.

Why must the DFS stage find a maximal set of vertex-disjoint paths rather than just one path?

If only a single shortest augmenting path of length l were augmented per phase (as in the Edmonds–Karp algorithm), other disjoint augmenting paths of the same length l would remain in the graph, so l would not increase after each phase and the runtime would revert to O(V E).

How does Hopcroft–Karp perform in practice on random and real-world graphs?

Although the worst-case bound is O(E √V), Bast, Mehlhorn, Schäfer, and Tamaki (2006) proved that on random sparse bipartite graphs the average shortest augmenting path length is O(log V), allowing Hopcroft–Karp to terminate in O(E log V) expected time—and even faster when warm-started with a greedy initial matching.

1. Hopcroft, J. E., & Karp, R. M. (1973). "An n^5/2 algorithm for maximum matchings in bipartite graphs." SIAM Journal on Computing, 2(4), 225–231. https://doi.org/10.1137/0202019
2. Berge, C. (1957). "Two theorems in graph theory." Proceedings of the National Academy of Sciences, 43(9), 842–844. https://doi.org/10.1073/pnas.43.9.842
3. Even, S., & Tarjan, R. E. (1975). "Network flow and testing graph connectivity." SIAM Journal on Computing, 4(4), 507–518. https://doi.org/10.1137/0204043
4. Bast, H., Mehlhorn, K., Schäfer, G., & Tamaki, H. (2006). "Matching algorithms are fast in sparse random graphs." Theory of Computing Systems, 39(1), 3–14. https://doi.org/10.1007/s00224-005-1254-y