Proofs: Hopcroft-Karp algorithm

Hopcroft-Karp runs in O((n + m) n^(1/2)) time full

This proof shows: time.worst.

Let $G = (X \cup Y, E)$ be bipartite with $n$ vertices and $m$ edges, and let $\nu = \nu(G)$. Each operation on an index, a label or a queue costs $O(1)$ on the word RAM.

One phase costs $O(n + m)$. Line L3 costs $O(|X|)$. In the search of lines L5 to L8, each vertex of $X$ enters the queue at most once, because it is enqueued only when its label changes from $\infty$, and its edges are scanned once when it leaves the queue: $O(n + m)$. Lines L10 and L11 cost $O(|X|)$ outside the calls. A call DFS($x$) sets $\text{dist}[x] = \infty$ in line L12 before it looks at any edge, and no call enters a vertex whose label is $\infty$, so each vertex of $X$ is entered at most once per phase. Each edge $xy$ is scanned at most once, in the single call on $x$, and the work of line L14 outside the inner call is $O(1)$ per edge. Line L15 runs once per vertex of $X$ on a found path, so at most $|X|$ times. The total is $O(n + m)$.

The number of phases. Let $D_t$ be the value $D$ of phase $t$. By Claim 4 of the correctness proof, a shortest augmenting path after phase $t$ has more than $2D_t - 1$ edges, and the length is odd, so $D_{t+1} \ge D_t + 1$. As $D_1 \ge 1$, phase $t$ has $D_t \ge t$ whenever it augments.

Let $M_t$ be the matching after phase $t$ and $M^*$ a maximum matching. The symmetric difference $M_t \triangle M^*$ contains $\nu - |M_t|$ vertex-disjoint $M_t$-augmenting paths (augmenting path). Each of them has at least $D_{t+1} \ge t + 1$ vertices of $Y$, hence at least $t + 1$ edges of $M^*$, and they are disjoint, so $(t + 1)(\nu - |M_t|) \le |M^*| = \nu$, that is, $\nu - |M_t| \le \nu / (t + 1)$.

If $\nu = 0$, the first phase has $D = \infty$ and is the only one. Otherwise take $t = \lfloor \sqrt \nu \rfloor$. If phase $t$ is reached and augments, then $\nu - |M_t| \le \nu / (\lfloor \sqrt \nu \rfloor + 1) < \sqrt \nu$, and each later phase that augments adds at least one edge, so fewer than $\sqrt \nu$ augmenting phases follow. In all cases there are at most $2\sqrt \nu$ augmenting phases, and one more phase that returns. Since $\nu \le n / 2$, the number of phases is at most $\sqrt{2n} + 1$.

Total. $O(\sqrt n)$ phases of $O(n + m)$ time give $O((n + m)\sqrt n)$ time, which is $O(m \sqrt n)$ when no vertex is isolated. The space is $\Theta(n + m)$: the adjacency lists, the arrays $\text{mate}$ and $\text{dist}$, the queue, and the path stack of at most $|X|$ entries. $\blacksquare$

Hopcroft-Karp returns a maximum matching full

This proof shows: correctness, termination.

Let $G = (X \cup Y, E)$ be a finite bipartite graph, every edge joining $X$ to $Y$. Fix one phase, let $M$ be the matching at its start, and let $\text{dist}$ and $D$ be the values computed by lines L3 to L8. An alternating path from a free vertex is a path $x_0\, y_1\, x_1\, y_2 \ldots$ with $x_0 \in X$ free, $x_{i-1} y_i \notin M$ and $y_i x_i \in M$.

Claim 1 (the layers). For every $x \in X$ with $\text{dist}[x] < \infty$, $\text{dist}[x]$ is the least number of matched edges on an alternating path from a free vertex to $x$; and $D$ is the least number of $Y$ vertices on an $M$-augmenting path, or $\infty$ if there is none. Proof. The search is a breadth-first search in the directed graph with an arc $x \to x'$ for each $y$ with $xy \in E \setminus M$ and $yx' \in M$, started from all free vertices of $X$ at distance 0. If $xy \in M$, then $\text{mate}[y] = x$, whose label is already finite, so line L8 adds nothing; hence line L8 follows exactly the arcs above. Breadth-first search dequeues the vertices in order of their distance, so every vertex at distance less than $D$ is expanded in line L6, and these distances are correct. An augmenting path has its ends in different sides, because its length is odd, so it has the form $x_0\, y_1 \ldots x_{k-1}\, y_k$ with $x_0$ and $y_k$ free; it is found at the moment its vertex $x_{k-1}$ is expanded, which gives $D \le k$, and line L7 sets $D$ only from such paths. $\square$

Claim 2 (each success flips an augmenting path). Within one phase, let $P_1, \ldots, P_j$ be the paths found by successful calls of line L11 so far, and $M_j = M \triangle P_1 \triangle \cdots \triangle P_j$. Then the paths are vertex-disjoint, each $P_i$ is an $M$-augmenting path with $D$ vertices of $Y$ whose $X$ vertices have labels $0, 1, \ldots, D - 1$, and $\text{mate}$ describes $M_j$. Proof. By induction on $j$. A call DFS($x_0$) from line L11 that succeeds follows a chain of calls DFS($x_0$), DFS($x_1$), ..., DFS($x_{D-1}$): line L14 enters $x_{i+1} = \text{mate}[y_{i+1}]$ only when its label is $d + 1$, so the entry labels are $0, 1, 2, \ldots$, and the last call succeeds through a free $y_D$ with $d + 1 = D$. The edges $x_i y_{i+1}$ are edges of $G$; the edges $y_{i+1} x_{i+1}$ are in $M_j$ at the time of the call. Every vertex $x$ entered in this phase got the label $\infty$ in line L12, so no vertex of $X$ is entered twice, and a vertex of $X$ on an earlier path $P_i$ is never entered again. A vertex $y$ of an earlier path is matched in $M_j$ to a vertex of $X$ on that path, whose label is $\infty$, so line L14 rejects it; in particular it is not free. Hence the new path shares no vertex with $P_1, \ldots, P_j$, its matched edges are edges of $M$, and $y_D$ and $x_0$ were free in $M$. So it is an $M$-augmenting path, and also an $M_j$-augmenting path. Line L15 runs for $x_{D-1}, \ldots, x_0$ on the way back and sets $\text{mate}[x_i] = y_{i+1}$ and $\text{mate}[y_{i+1}] = x_i$; this is exactly $M_j \triangle P_{j+1}$, because every vertex of the path is matched in the result to its neighbour on the path along an edge outside $M_j$. $\square$

Claim 3 (the set is maximal). At the end of a phase with $D < \infty$, every $M$-augmenting path with $D$ vertices of $Y$ shares a vertex with one of the paths found in the phase. Proof. Let $Q = x_0\, y_1\, x_1 \ldots x_{D-1}\, y_D$ be such a path and suppose it is disjoint from all the paths found. By Claim 1, $\text{dist}[x_i] = i$ for each $i$, since a shorter alternating path to $x_i$ followed by the rest of $Q$ would contain an augmenting path with fewer vertices of $Y$. The vertex $x_0$ is free and has label 0, so line L11 calls DFS($x_0$), unless it was entered earlier; either way $x_0$ is entered. Let $i$ be the largest index such that $x_i$ is entered in the phase. Since $x_i$ is on no path found, its call returned false, so line L13 scanned every edge of $x_i$, including $x_i y_{i+1}$, with $d = i$. If $i = D - 1$, the vertex $y_D$ was free at that time, because it is on no path found and the matching changes only along those paths, and $d + 1 = D$, so the call would have succeeded. If $i < D - 1$, then $\text{mate}[y_{i+1}] = x_{i+1}$ at that time, for the same reason. The label of $x_{i+1}$ was then $i + 1$ or $\infty$. If it was $i + 1$, line L14 entered $x_{i+1}$; if it was $\infty$, $x_{i+1}$ had been entered before. Both contradict the choice of $i$. $\square$

Claim 4 (augmenting paths grow). Let $\ell = 2D - 1$ and let $P_1, \ldots, P_k$, $k \ge 1$, be the paths found in a phase, with $M' = M \triangle P_1 \triangle \cdots \triangle P_k$. Then every $M'$-augmenting path has more than $\ell$ edges. Proof. Let $P$ be an $M'$-augmenting path. If $P$ shares no vertex with the $P_i$, its edges have the same status in $M$ and in $M'$, so it is $M$-augmenting with at least $\ell$ edges by Claim 1, and with exactly $\ell$ it would contradict Claim 3. So $|P| > \ell$. Otherwise, $P$ shares a vertex $v$ with some $P_i$. Every vertex of $P_i$ is matched in $M'$, by an edge of $P_i$, so $v$ is not an end of $P$, and $P$ contains the $M'$-edge at $v$, an edge of $P_i$. Now $N = M' \triangle P$ is a matching with $|M| + k + 1$ edges, and $M \triangle N = (P_1 \cup \cdots \cup P_k) \triangle P$, as sets of edges. The symmetric difference of two matchings is a union of vertex-disjoint paths and even cycles, and since $|N| - |M| = k + 1$ it contains at least $k + 1$ vertex-disjoint $M$-augmenting paths (augmenting path), each with at least $\ell$ edges. So $|(P_1 \cup \cdots \cup P_k) \triangle P| \ge (k + 1)\ell$. The left side equals $k\ell + |P| - 2|P \cap (P_1 \cup \cdots \cup P_k)| \le k\ell + |P| - 2$, since $P$ shares at least one edge with the $P_i$. Hence $|P| \ge \ell + 2 > \ell$. $\square$

Termination. If a phase has $D < \infty$, a shortest augmenting path $Q$ exists, and by Claim 3 it meets a path found in the phase, so at least one path is found and $|M|$ grows by one at least. A matching has at most $|X|$ edges, so after at most $|X| + 1$ phases line L9 returns.

Correctness. Line L9 returns only when $D = \infty$. By Claim 1 there is then no $M$-augmenting path, and by Berge's lemma $M$ is a maximum matching. By Claim 2, $\text{mate}$ describes $M$. $\blacksquare$