Hopcroft-Karp finds a maximum bipartite matching in O(E sqrt(V)). Explain where the square root comes from, in particular why only O(sqrt(V)) phases are needed and what each phase costs.

Hopcroft-Karp finds a maximum bipartite matching in O(E sqrt(V)). Explain where the square root comes from, in particular why only O(sqrt(V)) phases are needed and what each phase costs.

Approach: Each phase augments along a maximal set of shortest disjoint paths and lengthens the shortest augmenting path. Bound how many short augmenting paths can remain once that length is large.

O(E sqrt(V)) because each phase costs O(E) and the length of the shortest augmenting path strictly increases every phase, which caps the phase count at O(sqrt(V)). A phase runs one breadth first search to build the layered graph of shortest augmenting paths, then a depth first search that extracts a maximal set of vertex disjoint shortest augmenting paths, and both passes touch each edge a constant number of times. After the first sqrt(V) phases the shortest augmenting path has length at least sqrt(V). Take the symmetric difference of the current matching M and a maximum matching M*, which decomposes into vertex disjoint paths and cycles, and each augmenting path inside it holds at least sqrt(V) vertices, so at most V/sqrt(V) = sqrt(V) such paths exist. Each remaining phase raises the matching size by at least one, so at most sqrt(V) further phases run, and the two halves of the phase count add to O(sqrt(V)) at O(E) each.

Follow-up: What is the corresponding bound for general non-bipartite graphs and which structure makes that case harder?

Key concepts: augmenting path, vertex disjoint, symmetric difference, phase count.