Proofs: Kuhn's algorithm

Kuhn's algorithm returns a maximum matching full

This proof shows: correctness, termination.

Let $G = (L \cup R, E)$ be a bipartite graph, with every edge between $L$ and $R$. A matching $M$ is a set of edges without common ends. An $M$-alternating path is a path whose edges are alternately outside and inside $M$. An $M$-augmenting path is an $M$-alternating path of at least one edge whose two ends are both exposed (covered by no edge of $M$). If $P$ is $M$-augmenting, then $M \oplus P = (M \setminus P) \cup (P \setminus M)$ is a matching with one more edge. We use Berge's lemma: a matching is maximum if and only if it has no augmenting path.

Throughout, $M$ is the matching given by the arrays $\text{mate}_L$ and $\text{mate}_R$, which stay consistent: $\text{mate}_L[x] = v$ exactly when $\text{mate}_R[v] = x$. Line L1 makes $M = \emptyset$.

Lemma 1 (one search). Consider a call of TRY$(u)$ at line L4, where $u \in L$ is exposed and all marks are false. While the call runs, $M$ does not change until the first time line L10 runs. The call returns true if and only if $M$ has an augmenting path that starts at $u$, and in that case, on return, the new matching is $M \oplus P$ for an augmenting path $P$ from $u$.

Proof. Termination. Each call of TRY that is made from line L9 is made just after a right vertex $v$ is marked at line L8, and a vertex is marked at most once, because line L7 tests the mark. So the call makes at most $|R| + 1$ calls of TRY in total, and each call scans a finite list.

The calls follow alternating paths. While no call has returned true, $M$ does not change. At each moment the active calls are TRY$(x_0)$, TRY$(x_1)$, ..., TRY$(x_k)$ with $x_0 = u$, where TRY$(x_{i+1})$ was called by TRY$(x_i)$ at line L9 for a right vertex $v_i \in \text{Adj}[x_i]$ with $\text{mate}_R[v_i] = x_{i+1}$. The vertices $v_0, \ldots, v_{k-1}$ are distinct, as each was marked once. So the mates $x_1, \ldots, x_k$ are distinct, and none is $u$, which is exposed. Hence $x_0 v_0 x_1 v_1 \cdots x_k$ is a path whose edges $x_i v_i$ are not in $M$ (since $x_i$ is matched to $v_{i-1}$ or exposed) and whose edges $v_i x_{i+1}$ are in $M$: an $M$-alternating path from $u$.

If the call returns true. The first true value comes from TRY$(x_k)$ at line L9 for a vertex $v_k \in \text{Adj}[x_k]$ that is not marked before and has $\text{mate}_R[v_k] = $ nil. Then $P = x_0 v_0 x_1 v_1 \cdots x_k v_k$ is an alternating path with both ends exposed, so it is $M$-augmenting. Each TRY$(x_i)$ then runs line L10 with $v_i$ and returns true to its caller. After all of them, $\text{mate}_L[x_i] = v_i$ and $\text{mate}_R[v_i] = x_i$ for $0 \le i \le k$. The pairs $x_{i+1} v_i$ of $M$ are replaced by the pairs $x_i v_i$, and no other pair changes. This is $M \oplus P$.

If the call returns false. Then no line L10 ran, so $M$ did not change. Let $Z$ be the set of marked right vertices and $S = \{u\} \cup \{\text{mate}_R[v] : v \in Z\}$. Each $v \in Z$ is matched: an exposed marked vertex makes the test of line L9 true. TRY was called on each vertex of $S$: on $u$ at line L4, and on $\text{mate}_R[v]$ right after $v$ was marked. Each of these calls returned false, so it ran its loop to the end, and each neighbour $v$ of its vertex was marked, by this call or earlier. So $N(S) \subseteq Z$. Now let $Q = u\,w_1 y_1 w_2 y_2 \ldots$ be any $M$-alternating path from $u$. Its first edge is not in $M$, as $u$ is exposed, so $w_1 \in N(u) \subseteq Z$. Since $G$ is bipartite, the vertices of $Q$ alternate between $R$ and $L$; the edges from $R$ to $L$ are in $M$, and the edges from $L$ to $R$ are not. By induction along $Q$: if $w_i \in Z$, then $w_i$ is matched and $y_i = \text{mate}_R[w_i] \in S$, and then $w_{i+1} \in N(y_i) \subseteq Z$. So every right vertex of $Q$ is in $Z$ and is matched, and every left vertex of $Q$ other than $u$ is matched as well. So $Q$ does not end at an exposed vertex other than $u$, and it is not augmenting. $\square$

Lemma 2 (dead vertices stay dead). Let $M$ be a matching, $u$ a vertex exposed by $M$ such that $M$ has no augmenting path with $u$ as an end, and $P$ an $M$-augmenting path. Then $u$ is exposed by $M' = M \oplus P$, and $M'$ has no augmenting path with $u$ as an end.

Proof. The ends of $P$ are exposed by $M$ and are not $u$, by the hypothesis. The inner vertices of $P$ are covered by $M$, so $u$ is not on $P$, and $u$ stays exposed. Every vertex of $P$ is covered by $M'$ by an edge of $P$.

Assume that $Q$ is an $M'$-augmenting path with the end $u$. If $Q$ has no vertex on $P$, then no edge of $Q$ is in $P$, and $M$ and $M'$ agree on the edges of $Q$, so $Q$ is $M$-augmenting with end $u$, a contradiction. Otherwise, let $x$ be the first vertex of $Q$, counted from $u$, that is on $P$, and let $Q_1$ be the part of $Q$ from $u$ to $x$. The edges of $Q_1$ have at most the end $x$ on $P$, so none is an edge of $P$, and $M$ and $M'$ agree on them. The last edge of $Q_1$ ends at $x$ and is not in $P$; the $M'$-edge at $x$ is in $P$; so the last edge of $Q_1$ is not in $M'$, and not in $M$. So $Q_1$ is an $M$-alternating path from $u$ whose first and last edges are outside $M$.

If $x$ is an end of $P$, it is exposed by $M$, and $Q_1$ is $M$-augmenting with end $u$, a contradiction. Otherwise $x$ is an inner vertex of $P$, and the $M$-edge at $x$ is on $P$. Let $P_1$ be the part of $P$ from $x$ that starts with this $M$-edge, up to the end of $P$ in that direction. $P_1$ is $M$-alternating, starts with an edge of $M$ and ends at an end of $P$, which is exposed by $M$. The paths $Q_1$ and $P_1$ share only $x$, because $Q_1$ meets $P$ only at $x$. So $Q_1 P_1$ is a path from $u$ to an $M$-exposed vertex other than $u$, and it alternates at $x$, because the last edge of $Q_1$ is outside $M$ and the first edge of $P_1$ is in $M$. It is $M$-augmenting with end $u$, a contradiction. $\square$

Theorem. KUHN stops and returns a maximum matching of $G$.

Proof. Each round stops by Lemma 1, and there are $|L|$ rounds. Each round changes $M$ only by an augmentation (Lemma 1), so $M$ is always a matching. Call a left vertex dead when it is exposed and the current matching has no augmenting path with it as an end.

We show by induction on the rounds: after the round of $u$, every left vertex handled so far is matched or dead. Before the round of $u$, $u$ is exposed: the augmentation of the round of an earlier vertex $x$ newly covers only $x$ and one right vertex. By Lemma 1, the round either matches $u$, or it fails, and then $u$ is dead. A matched left vertex stays matched, because an augmentation only adds covered vertices. A dead vertex stays dead after an augmentation, by Lemma 2, and a failed round does not change $M$.

At the end every left vertex is matched or dead. Assume that $M$ has an augmenting path $P$. Its two ends are exposed, and it has an odd number of edges, so, as $G$ is bipartite, one end is in $L$. That end is an exposed left vertex, so it is dead, and no augmenting path has it as an end, a contradiction. So $M$ has no augmenting path, and by Berge's lemma it is a maximum matching. $\blacksquare$