Maximum matching in a general graph — pair up as many vertices as possible, no vertex twice. Odd cycles break the simple approach, so Edmonds’ trick is to shrink each odd cycle (a blossom) into a single node, match in the smaller graph, then expand. Its 1965 paper is where computer science first argued that “polynomial time” means “tractable.”
THE TECHNIQUE find augmenting paths, shrink the blossoms
Grow alternating trees from unmatched vertices, seeking an augmenting path (unmatched-matched-unmatched-…-unmatched) — flipping it grows the matching by one. The obstruction is an odd cycle; Edmonds contracts it to one node, continues, and later expands it. Below: a graph, its maximum matching, and a blossom highlighted. live demo
HISTORY & CREDIT where 'good algorithm' got its meaning
“Just another matching routine” — it is routine the paper that defined efficiency: Edmonds argued a “good” algorithm is a polynomial-time one. cited
1957 · Claude Berge gives the augmenting-path characterisation: a matching is maximum iff it has no augmenting path. 1965 · Jack Edmonds, “Paths, Trees, and Flowers” — the blossom contraction makes general-graph matching polynomial, and the paper articulates that polynomial-time = tractable (the intuition behind the class P). the shrink · an odd cycle with the right alternation is a blossom; contract it to a single vertex, find the path, then unfold — the move bipartite matching never needs. 1980 · Micali & Vazirani reach O(√V E) — faster, same idea.
Before this paper, “solvable” had no agreed cost; after it, tractability had a definition. Edmonds 1965
RECOMMEND FOR I-13 matching on integer arrays
The matching, the trees, and the blossom bases are all integer arrays — and the maximum matching comes out on the compiler:
$ i13 run match.i13 # the 5-cycle C5
matched = 4 size = 2 # maximum matching of an odd 5-cycle is 2 edges
Recommend:nothing new for the substrate — match[], parent[], base[] are bounded integer arrays, and the whole algorithm is array reads/writes and recursion (verified: C5’s maximum matching is 2). The blossom contraction is index bookkeeping — relabel a cycle’s vertices to a shared base — not a new value kind. Note: the honest wall is the same as the trees’ — a rich adjacency structure wants real linked nodes (PS-015) or a 2-D array (PS-004); the flattened edge-list / parallel-array form runs today, exactly as here.