Chapter 13 · Matching
General Matching and Blossoms
Why odd cycles break the bipartite algorithm, what a blossom is, Edmonds' contraction, and the Tutte/Berge formulas.
#Blossoms: why bipartite logic dies
Given a matching M in an arbitrary graph, a blossom is an odd cycle C with |C| = 2k+1 together with a vertex b ∈ C (its base) such that the path from b along C in either direction is alternating starting with a matched edge... equivalently: C has k matched edges, and the two edges of C incident to b are both unmatched. Contracting C into a single vertex preserves matchings up to one extra matched edge.
Take K3 with M = {uv} and a free vertex w. Searching for an augmenting path from w: w → u (unmatched), then from u the only way onward is the matched edge uv, landing on v, and from v the unmatched edge vw returns to the start. The alternating walk is a cycle of odd length — so "reachable" sets become inconsistent: the same vertex is reached at both even and odd distance, and the DFS's used marker either loops forever or refuses a legitimate augmentation. Blossoms are exactly these odd cycles; the fix is to contract each one, keep searching in the smaller graph, and expand the answer afterwards.
#Edmonds' matching theorem
A graph has a perfect matching iff for every U ⊆ V, the number of odd components of G - U is at most |U|. (Tutte's 1-factor theorem; equivalently, the maximum matching has size tfrac12 minU (n - o(G-U) + |U|) — Berge–Edmonds formula.)
Necessity: in a perfect matching, each odd component of G-U must send at least one edge into U, and those edges are distinct per component, so |U| ≥ o(G-U). Sufficiency: contrapositive via the algorithm — if the search for an augmenting path fails in the maximal-augmentation state, the set U of bases of the blossoms/outer vertices reached by the alternating forest violates the condition: every odd component of G - U is a contracted blossom with all its vertices matched internally, and each outer vertex of U accounts for at most one such component. The construction of U from the failed search is the certificate, which is why the theorem is a proof of existence and the algorithm's correctness argument at once. ∎
#What to implement, realistically
What to implement, realistically
- O(V3) Edmonds with union-find + explicit contraction: ~70 lines; correct, slow constant; use when V ≤ 500,
- O(V E) blossom growth without global contraction (the "labb, maxlab" Gabow style): faster, but 3× the code,
- randomised algebraic approach: the Tutte matrix over a large field, rank = 2 · (max matching size); O(nω) with Gaussian elimination, ~25 lines, and it answers "is there a perfect matching", "which edges are allowed", and "the size" with a one-sided error of 2-30 per trial. This is often the shortest correct solution in a contest, at the price of a probabilistic argument you must be able to state,
- for the special cases: a tree (DP, Matching: Definitions and Duality problems), a cactus, a planar graph with small faces (Kasteleyn/Pfaffian for counting), or general graphs where maximum matching is only needed for "does a near-perfect matching exist" (then the greedy maximal matching plus a few augmentations usually passes, but has no guarantee — do not rely on it).
// find-augmenting-path with blossom contraction, O(V*E) per search:
// base[v], p[v], q = BFS queue of "outer" vertices
// lca(a, b): walk up via p[] marking used[] to find the blossom base
// mark_path(v, b, children): walk v up to b, contracting each vertex on the way
// when an edge (a,b) joins two outer vertices of different trees:
// if lca(a,b) is undefined -> augment along a + path to root + b
// else -> blossoms: mark_path(a,b,a), mark_path(b,a,b) and enqueue contracted vertices
int lca(int a, int b) {
static vector<bool> used(n); fill(used.begin(), used.end(), false);
for (;;) { a = base[a]; used[a] = true; if (!match[a]) break; a = p[match[a]]; }
for (;;) { b = base[b]; if (used[b]) return b; b = p[match[b]]; }
}
void mark_path(int v, int b, int children) {
while (base[v] != b) {
blossom[base[v]] = blossom[base[match[v]]] = true;
p[v] = children; children = match[v];
if (!used[match[v]]) { used[match[v]] = true; q.push(match[v]); }
v = p[match[v]];
}
}#The three implementation cliffs
lcamust be recomputed on contracted bases (a = base[a]inside the loop) — using original vertices makes the base wrong and the augmentation invalid;- when a blossom is contracted, the parity of everything inside flips: the
mark_pathloop must mark both endpoints of each matched pair inside the blossom as in-blossom, or the same blossom is rediscovered forever; - after finding an augmenting path in the contracted graph you must expand blossoms one by one (each expansion rotates the internal matching by one edge) — this post-processing is where a hand-written implementation is more error-prone than the search itself, and it is why many teams prefer the randomised rank method instead.
#Weighted general matching
Maximum-weight matching in a general graph = the blossom algorithm with weights (Edmonds' primal–dual), O(V2 · something), and effectively unimplementable in a contest. Two escape routes that are real: (a) if the graph is bipartite, use Hungarian / min-cost flow (The Hungarian Algorithm, Min-Cost Max-Flow); (b) if weights are on vertices or the objective is "maximise the number of matched pairs with a bonus", reduce to min-cost flow on a bipartite relaxation and check the relaxation is integral for your instance class. Otherwise the problem is almost certainly not asking for weighted general matching.