Hopcroft-Karp Matching

The fastest classical algorithm for maximum matching in bipartite graphs, augmenting many shortest paths per phase.

Bipartite matching

In a bipartite graph with parts L and R, a matching pairs vertices across the parts so no vertex is used twice; a maximum matching pairs as many as possible. Simple augmenting-path matching runs in O(V * E). Hopcroft-Karp improves this to O(E * sqrt(V)) by processing many disjoint shortest augmenting paths at once.

Phase structure

Kronos motion — classical

Each phase runs a BFS from all free left vertices to compute the length of the shortest augmenting path, then a DFS finds a maximal set of vertex-disjoint augmenting paths of that length and flips them all. The shortest augmenting-path length strictly increases each phase, and after O(sqrt(V)) phases the remaining paths are long enough that only O(sqrt(V)) more can exist, bounding total phases by O(sqrt(V)).

Skeleton

python

import math

def hopcroft_karp(adj, nL, nR):
    INF = math.inf
    matchL = [-1]*nL
    matchR = [-1]*nR
    result = 0
    while bfs(adj, matchL, matchR, dist):
        for u in range(nL):
            if matchL[u] == -1 and dfs(u, adj, matchL, matchR, dist):
                result += 1
    return result

Equivalence to flow

Bipartite matching is a unit-capacity max-flow problem: add a source into L, a sink out of R, and capacity-1 edges. Dinic's algorithm on that network is exactly Hopcroft-Karp and achieves the same O(E * sqrt(V)) bound, since blocking flows correspond to disjoint shortest augmenting paths.

Uses

Assignment of tasks to workers with 0/1 feasibility.
Minimum vertex cover and maximum independent set on bipartite graphs via Koenig's theorem.
Chain decompositions and Dilworth's theorem on partial orders.