Proofs: Edmonds' blossom algorithm

Edmonds' blossom algorithm runs in O(n^3) time full

This proof shows: time.worst.

Let $G$ have $n$ vertices and $m$ edges. The graph $G'$ is represented as in the implementation: the adjacency lists of $G$, an array $\text{base}$, the labels, the tree of each vertex, the array $\text{mate}$, and parent links. Each array access and comparison costs $O(1)$ on the word RAM.

Phases. By the termination argument of the correctness proof there are at most $\lfloor n/2 \rfloor + 1$ phases.

Scanning. In one phase each vertex is enqueued at most once, and when dequeued it scans its adjacency list once. The test of line L6 compares $\text{base}[v]$ with $\text{base}[w]$ and $\text{mate}[v]$ with $w$, line L7 reads two labels and two tree names, and line L11 sets a constant number of entries. So the scans cost $O(n + m)$ per phase, apart from the work of lines L8 and L10.

Contractions. Each contraction replaces the vertices of an odd cycle of $G'$, at least three of them, by one, so the number of vertices of $G'$ drops by at least 2, and there are at most $n/2$ contractions per phase. A contraction finds the base by walking from $v$ to the root and from $w$ upwards until the first marked vertex, following $\text{mate}$, the parent links and $\text{base}$: $O(n)$ steps. Marking the two paths costs $O(n)$, and the loop that sets $\text{base}[x] \leftarrow b$ for the vertices of the blossom and enqueues the formerly inner ones visits all $n$ vertices once: $O(n)$. So the contractions cost $O(n^2)$ per phase.

Augmentation. Line L8 follows $\text{mate}$ and the links from $v$ and from $w$ to their roots; each step visits a new vertex of the path, so this costs $O(n)$, and flipping the path costs $O(n)$ too.

Total. One phase costs $O(n + m + n^2) = O(n^2 + m)$, and all phases $O(n(n^2 + m))$. For a simple graph $m \le n^2/2$, which gives $O(n^3)$. The space is $\Theta(n + m)$: the adjacency lists and a constant number of arrays of length $n$, plus the queue, which holds each vertex at most once per phase. $\blacksquare$

Edmonds' blossom algorithm returns a maximum matching full

This proof shows: correctness, termination.

Let $G = (V, E)$ be a finite graph and $M$ the matching at the start of a phase; $M$ does not change until line L8. Write $G_0 = G$, $M_0 = M$, and let $G_i$, $M_i$ be the graph and matching after the $i$-th contraction of the phase, so that $G_i = G_{i-1}/B_i$ and $M_i = M_{i-1} \setminus E(B_i)$. A vertex of $G_i$ is a set of vertices of $G$, the set with a common value of $\text{base}$.

Claim 1 (the forest). At every moment of a phase, with $G' = G_i$ and $M' = M_i$: the labelled vertices of $G'$ form an alternating forest $F$ with one tree per free vertex of $G'$, rooted at it; every path in $F$ from a root to an outer vertex is $M'$-alternating, of even length, and ends with a matched edge or has no edge; each inner vertex is a single vertex of $G$, with exactly one child, its partner, which is outer; and each vertex of $G'$ that is a contracted set is outer and has an odd number of vertices of $G$. Proof. Line L3 makes every free vertex a root and nothing else is labelled. Line L11 adds an unmatched edge from an outer $v$ to an unlabelled $w$; $w$ is matched, because every free vertex is a root, and its partner is unlabelled too, because the partner of a labelled vertex is labelled (its parent or its child, or none for a root). So the tree grows by a path of two edges, unmatched then matched, and the claim is kept. In line L10, $v$ and $w$ are outer in the same tree; by the blossom page, the two tree paths to their lowest common ancestor $b$ and the edge $vw$ form a blossom $B$ with base $b$, an outer vertex, and stem the tree path from the root to $b$. Contracting $B$ replaces it by one vertex $\beta$, which is matched by the stem edge of $b$ or is the root. The tree minus the vertices of $B$, with $\beta$ in the place of $b$, is still an alternating tree: every inner vertex of $B$ had its parent and its child in $B$, and every other child of a vertex of $B$ now hangs from $\beta$ by the same unmatched edge. $\beta$ is outer, and it consists of an odd number of odd sets, so it is odd. $\square$

Claim 2 (lifting). Let $B$ be a blossom of $M_{i-1}$ in $G_{i-1}$ with base $b$, whose stem starts at a free vertex, and let $P'$ be an $M_i$-augmenting path in $G_i = G_{i-1}/B$. Replacing the vertex $\beta$ of $B$ on $P'$ by a suitable path in $B$ gives an $M_{i-1}$-augmenting path in $G_{i-1}$. Proof. If $\beta \notin P'$ there is nothing to do. Otherwise, $P'$ has one edge at $\beta$ that is not matched and comes from an edge $xy$ of $G_{i-1}$ with $x \in B$ and $y \notin B$; and either $\beta$ is an end of $P'$, so it is free and $b$ is free, or $\beta$ is an inner vertex of $P'$, whose other edge is the matched edge $e_b$ of $b$. In both cases replace $\beta$ by the way round $B$ from $b$ to $x$ that has even length, which is empty if $x = b$. This way starts at $b$ with an unmatched edge, because both edges of $B$ at $b$ are unmatched, and ends at $x$ with a matched edge, because it alternates and has even length. So at $b$ the matched edge $e_b$, if present, is followed by an unmatched edge, and at $x$ a matched edge is followed by the unmatched edge $xy$. If $x \ne b$, the edge $xy$ is unmatched since the matched edge of $x$ lies in $B$; if $x = b$, $xy$ is the unmatched edge of $P'$. The vertices of $B$ appear only in the inserted part, so the result is a path, it alternates, and its ends are the free ends of $P'$, or $b$ in place of the free $\beta$. $\square$

Claim 3 (augmentation). When line L8 runs, $P$ is an $M$-augmenting path of $G$, so $M \triangle P$ is a matching with one more edge. Proof. Let $G' = G_k$. The vertices $v$ and $w$ lie in outer vertices of $G'$ in different trees, so by Claim 1 the tree path from the root of $v$ to $v$ and from $w$ to its root are even alternating paths from free vertices that end with matched edges, and they are vertex-disjoint. The edge $vw$ is not matched, since a matched edge at an outer vertex goes to its parent or child in the same tree. So $P'$ is an $M_k$-augmenting path of $G_k$. Applying Claim 2 for $i = k, k - 1, \ldots, 1$ expands $B_k, \ldots, B_1$ in turn and gives an $M$-augmenting path $P$ of $G$; each $B_i$ satisfies the hypothesis by Claim 1. By the flipping rule for augmenting paths, $M \triangle P$ is a matching of size $|M| + 1$. $\square$

Claim 4 (the end of a failing phase). Suppose a phase ends with $Q$ empty and no augmentation. Then every edge $xz$ of $G$ with $x$ in an outer vertex $X$ of $G'$ has $z \in X$ or $z$ inner. Proof. A vertex of $G$ is enqueued when it first lies in an outer vertex of $G'$: as a root in line L3, as a partner in line L11, or as a formerly inner vertex in line L10, and it stays in an outer vertex afterwards. So $x$ was dequeued and scanned the edge $xz$ at a time when it was already outer. Consider the state of $z$ then. If $z$ was in the same vertex of $G'$, it still is, since vertices of $G'$ only merge. If $xz \in M$, then $z$ is the parent or the child of $x$'s vertex in the tree, or in the same vertex; a blossom that contains an inner vertex contains its child and the vertex of its parent, so $z$ is now inner or in the same vertex as $x$. If $z$ was outer, line L7 or L9 applied: the first is excluded by hypothesis, and the second merged the two. If $z$ was unlabelled, line L11 made it inner with parent $x$'s vertex; if it later became outer, it did so in a blossom, which then also contains its parent's vertex, so $z$ is in the same vertex as $x$. If $z$ was inner and later became outer, then $z$ was enqueued again and scanned the edge $zx$ while $x$ was outer, so by the previous cases they are now in one vertex. Otherwise $z$ is still inner. $\square$

Claim 5 (maximality). If a phase ends without augmenting, $M$ is a maximum matching. Proof. Let $U$ be the set of inner vertices, each a single vertex of $G$, and let $\mathcal O$ be the set of outer vertices of $G'$. By Claim 4, each $X \in \mathcal O$ is joined only to vertices of $U$ and to itself, and $X$ is connected, as a nest of contracted cycles; so each $X$ is a component of $G - U$, with an odd number of vertices by Claim 1. Hence $\text{odd}(G - U) \ge |\mathcal O|$. In each tree of $F$ every inner vertex has exactly one child and every outer vertex except the root has an inner parent, so the tree has one more outer vertex than inner vertices, and $|\mathcal O| - |U|$ is the number of trees, which is the number $f$ of free vertices of $M$ in $G$. For any matching $N$ and any set $U$, each odd component of $G - U$ has a vertex that is not matched by $N$ inside the component, so it is free or matched to $U$; at most $|U|$ are matched to $U$, so $N$ leaves at least $\text{odd}(G - U) - |U|$ vertices free, and $|N| \le \frac{1}{2}(n - \text{odd}(G - U) + |U|)$. With our $U$ this gives $|N| \le \frac{1}{2}(n - |\mathcal O| + |U|) = \frac{1}{2}(n - f) = |M|$. $\square$

Termination. Inside a phase each vertex is enqueued at most once, since it is enqueued only when it first becomes outer, so the loop of lines L4 to L11 ends. Each phase that augments raises $|M|$ by one, by Claim 3, and $|M| \le n/2$, so at most $\lfloor n/2 \rfloor + 1$ phases run.

Correctness. The algorithm stops only after a phase without augmentation, and then $M$ is maximum by Claim 5. $\blacksquare$