Blossom Algorithm

Blossom algorithm (also known as Edmonds's matching algorithm) is a landmark polynomial-time graph algorithm in computation and algorithms discovered by Jack Edmonds in 1965 for constructing a maximum-cardinality or maximum-weight matching in a general (non-bipartite) undirected graph G = (V, E). Prior to Edmonds's 1965 paper "Paths, Trees, and Flowers", efficient augmenting-path methods such as the Ford–Fulkerson algorithm and the Hungarian algorithm were restricted to bipartite graphs because non-bipartite graphs contain odd-length cycles, which cause naive alternating-path searches to traverse vertices in both even and odd parity states and miss valid augmenting paths or report self-intersecting non-simple walks.

Edmonds resolved this obstacle by proving that whenever an alternating tree search encounters an odd-length alternating cycle—which he termed a blossom—the entire odd cycle can be contracted (shrunk) into a single pseudovertex while preserving the existence of augmenting paths. Furthermore, in that same 1965 paper, Edmonds explicitly formulated the thesis that polynomial-time solvability constitutes the mathematical definition of an "efficient" or "good" algorithm, laying a cornerstone of modern computational complexity theory.

Odd Cycles and the Failure of Naive Alternating Search

Let G = (V, E) be an undirected graph with vertex count V = |V| and edge count E = |E|, and let M ⊆ E be a matching. By Berge's Lemma (1957), M is a maximum-cardinality matching if and only if G contains no M-augmenting path—a simple path whose edges alternate between free edges (E \ M) and matched edges (M) and whose endpoints are two distinct unmatched (free) vertices.

In a bipartite graph (which contains no odd cycles), building an alternating forest F rooted at the free vertices partitions all reached vertices cleanly into even (outer) vertices (at even path length from a root, reached via a matched edge) and odd (inner) vertices (at odd path length from a root, reached via a free edge). In a non-bipartite graph, however, a free edge {u, v} ∈ E \ M can connect two outer vertices u and v that belong to the same alternating tree T ⊆ F. Tracing the unique tree paths from u and v back to their lowest common ancestor b ∈ T (the base of the cycle) reveals an odd-length cycle B of length 2k + 1 (for k ≥ 1). Within B, a naive single-visit search labels vertices with a single parity, blocking the opposite-direction traversal around B required to reach an exposed vertex downstream.

Definition of a Blossom and the Contraction Invariant

Formally, given a matching M, a blossom B is an odd-length cycle of 2k + 1 vertices containing k matched edges in M and k + 1 free edges in E \ M, such that the unique vertex b ∈ B not incident to any matched edge inside B (the base of the blossom) is connected to a free root vertex r by an even-length alternating path S (the stem, possibly of length 0 if b = r).

Let G / B denote the contracted graph obtained by shrinking all 2k + 1 vertices of B into a single new pseudovertex v_B and deleting self-loops inside B, with contracted matching M / B = M \ E(B). Because b is the only vertex of B that can be incident to a matched edge in M \ E(B), M / B is a valid matching in G / B, and v_B is an outer (even) vertex in the contracted alternating tree. Edmonds proved the Blossom Contraction Theorem:

A matching M has an M-augmenting path in G if and only if the contracted matching M / B has an (M / B)-augmenting path in the contracted graph G / B.

Lifting an Augmenting Path: Suppose P′ is an (M / B)-augmenting path in G / B that passes through the pseudovertex v_B. Since v_B is either free (if the base b was a free root) or incident to the single matched stem edge entering b, P′ enters (or starts at) B via b and exits B via some free edge {x, y} ∈ E \ M with x ∈ B and y ∉ B. Because B is an odd cycle of 2k + 1 vertices whose edges excluding b are paired in M, traversing B from b to x in one of the two circular directions (clockwise or counterclockwise) has even length and ends with a matched edge in M, whereas the opposite direction has odd length and ends with a free edge. Splicing the even-length arc of B from b to x into P′ lifts P′ to a valid simple M-augmenting path P in G.

The Tutte–Berge Formula and Gallai–Edmonds Decomposition

When Edmonds's algorithm terminates with no augmenting path, the final alternating forest F (with all blossoms unshrunk into the set O of outer vertices and I of inner vertices) provides a constructive proof of the Tutte–Berge Formula (1958):

where odd(G \ U) denotes the number of connected components of odd cardinality in G \ U. Choosing U = I (the inner vertices of the final Hungarian forest) achieves exact equality, establishing strong min-max duality for non-bipartite matching and defining the canonical Gallai–Edmonds structure decomposition.

Edmonds's Alternating Forest Search

In each augmentation phase, the algorithm initializes an alternating forest F whose roots are all unmatched vertices (labeled outer / even) and scans unscanned outer vertices u:

1. Grow Step: If u has a free edge {u, v} to an unvisited vertex v (which must be matched to some w by M, else Step 2 applies), add (u, v) (with v labeled inner / odd) and the matched edge (v, w) (with w labeled outer / even) to F.
2. Augment Step: If u has a free edge {u, v} to an outer vertex v lying in a different tree of F, concatenate the root-to-u path, edge {u, v}, and v-to-root path, recursively expand (lift) any contracted blossoms along the path, and augment M ← M ⊕ P.
3. Shrink (Contract) Step: If u has a free edge {u, v} to an outer vertex v lying in the same tree of F, find the lowest common ancestor b of u and v in F, contract the odd cycle B into an outer pseudovertex v_B (often tracked implicitly via a disjoint-set data structure maintaining blossom bases), and enqueue any newly outer vertices of B for scanning.

Complexity Improvements from O(V⁴) to O(E√V)

Edmonds's original 1965 analysis performed up to O(V) contractions per phase in O(V²) time each, yielding O(V⁴) total time (or O(V²E)). Subsequent algorithmic breakthroughs reduced both unweighted and weighted general matching to match their bipartite counterparts:

For maximum-weight general matching, Edmonds proved that the matching polytope on non-bipartite graphs requires adding odd-set blossom inequalities ∑_{e ∈ E(B)} x_e ≤ (|B| − 1)/2 for every odd subset B ⊆ V (|B| = 2k + 1), accompanied by non-negative dual blossom potentials z_B ≥ 0 that are incremented on outer blossoms and decremented on inner blossoms.

1. Chinese Postman Problem (Route Inspection) and Christofides's TSP Approximation: Both Eulerian graph augmentation (making all vertex degrees even before running Hierholzer's algorithm) and Nicos Christofides's 3/2-approximation algorithm for the metric Traveling Salesperson Problem compute a minimum-weight perfect matching on the odd-degree vertices of a graph (or of a minimum spanning tree) using the weighted blossom algorithm.
2. Quantum Error Correction (Surface Code Decoding): In fault-tolerant superconducting and neutral-atom quantum computing, syndrome defects on topological surface codes occur in pairs along space-time error chains; real-time decoders (PyMatching, Blossom V) pair syndrome defects via minimum-weight perfect matching in non-bipartite syndrome graphs.
3. Organic Chemistry and Kekulé Structure Enumeration: In computational chemistry, carbon skeleton graphs containing five- and seven-membered rings (fullerenes, azulenes, polycyclic aromatic hydrocarbons) are non-bipartite, requiring Edmonds's blossom algorithm to identify Kekulé π-bond matchings and radical sites.

Why can't the Hungarian algorithm or Hopcroft–Karp be applied directly to non-bipartite graphs?

In a non-bipartite graph, the incidence matrix is not totally unimodular (its linear programming relaxation has fractional half-integral vertices around odd cycles, such as assigning 0.5 to each edge of a triangle), and odd cycles allow vertices to be reachable by both even-length and odd-length alternating paths from the same root.

How does the Micali–Vazirani algorithm achieve O(E√V) time?

Silvio Micali and Vijay Vazirani (1980) generalized the phase structure of the Hopcroft–Karp algorithm to non-bipartite graphs by maintaining both minimum even-level and minimum odd-level labels for every vertex and using synchronized two-finger Depth-First Searches across "bridge" edges to contract blossoms and extract a maximal set of shortest vertex-disjoint augmenting paths in O(E) time per phase across O(√V) phases.

1. Edmonds, J. (1965). "Paths, trees, and flowers." Canadian Journal of Mathematics, 17, 449–467. https://doi.org/10.4153/CJM-1965-045-4
2. Edmonds, J. (1965). "Maximum matching and a polyhedron with 0,1-vertices." Journal of Research of the National Bureau of Standards Section B, 69B(1–2), 125–130. https://doi.org/10.6028/jres.069B.013
3. Micali, S., & Vazirani, V. V. (1980). "An O(√|V| · |E|) algorithm for finding maximum matching in general graphs." Proceedings of the 21st Annual Symposium on Foundations of Computer Science (FOCS), 17–27. https://doi.org/10.1109/SFCS.1980.12
4. Gabow, H. N. (1990). "Data structures for weighted matching and nearest common ancestors with linking." Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 434–443. https://dl.acm.org/doi/10.5555/320176.320229
5. Kolmogorov, V. (2009). "Blossom V: A new implementation of a minimum cost perfect matching algorithm." Mathematical Programming Computation, 1(1), 43–67. https://doi.org/10.1007/s12532-009-0002-8