Blossom Algorithm: Maximum Matching in General Graphs

The problem: why odd cycles break simple matching

A matching M in a graph is a set of edges sharing no endpoints. Growing a matching relies on an augmenting path: a path that starts and ends at unmatched vertices and alternates unmatched, matched, unmatched edges. Flip every edge along it (matched becomes unmatched and vice versa) and the matching grows by exactly one. Berge's theorem guarantees a matching is maximum if and only if no augmenting path exists — so the whole game is finding augmenting paths.

In bipartite graphs a simple BFS/DFS finds them reliably, because alternating-path parity is unambiguous. In general graphs an odd cycle wrecks this. Consider a triangle where two edges must alternate around it: a vertex can be reached by both an even-length and an odd-length alternating walk simultaneously. The naive search commits to one parity, misses valid augmentations, and reports a matching that is too small.

• Bipartite: no odd cycles, parity is well-defined, augmenting search just works.
• General: odd cycles create parity ambiguity — the core difficulty Edmonds solved.

How it works: grow a forest, contract the blossom

The algorithm builds an alternating forest rooted at every exposed (unmatched) vertex. Vertices get parity labels: even (outer, reachable by an even-length alternating path from a root) and odd (inner). It scans edges from even vertices:

• Even → unlabeled matched vertex: extend the tree (add the vertex as odd, its match as even).
• Even → even in a different tree: an augmenting path is found — flip it, restart.
• Even → even in the same tree: a blossom — an odd cycle through the two vertices' lowest common ancestor.

find_augmenting_path(G, M):
  forest = {exposed vertices as even roots}
  while some even vertex v has an unscanned edge (v,w):
    if w unlabeled:      add w (odd) and match(w) (even) to forest
    elif w is even, different tree:  return path(v)+path(w)  # augment
    elif w is even, same tree:       B = blossom(v,w)
                                     contract B into super-vertex
                                     recurse on contracted graph
  return none  # matching is maximum (Berge)

Contracting the blossom into one super-vertex removes the parity ambiguity. When the recursion finds an augmenting path through the super-vertex, it is lifted back: expand the blossom and route the path around the correct side of the odd cycle.

Complexity and a worked trace

Each augmentation increases the matching by one, so there are at most V/2 augmentations. One search for an augmenting path — including finding and contracting blossoms — costs O(V·E) naively, giving O(V^2·E) or roughly O(V^4) for dense graphs (Edmonds' original bound). Using a labeling scheme that never physically shrinks the graph (Gabow 1976), a search runs in O(V^2) and the total drops to O(V^3), the common textbook and library bound. The theoretical champion is Micali-Vazirani (1980) at O(E·√V), which finds many shortest augmenting paths per phase. Space is O(V + E).

Trace on a triangle plus a pendant: vertices A-B-C form a triangle; D hangs off A. Start empty. Match B-C. Now A and D are exposed; root the forest at A. Edge A-B: B becomes odd, its match C becomes even. Edge C-A: both A and C are even in the same tree — blossom {A,B,C}. Contract to super-vertex S. Now S-D is an edge between two exposed vertices: augment. Lifting the blossom, the real augmenting path is D-A, and we route B-C untouched — final matching {D-A, B-C}, size 2, which is maximum.

Where it is used in real systems

General-graph matching appears wherever pairings are symmetric (unlike bipartite job-to-worker assignment):

• Kidney-exchange programs. Patient-donor pairs form a general graph; a maximum (weighted) matching maximizes life-saving transplants. Production matching engines run Edmonds-style algorithms, often the weighted variant.
• VLSI and EDA. Chip-layout and via-minimization steps reduce to matching on non-bipartite grids.
• Christofides' TSP approximation. Its 3/2-approximation for metric TSP needs a minimum-weight perfect matching on odd-degree vertices — a weighted blossom computation is the workhorse step.
• Scheduling and sports leagues. Round-robin pairing, task pairing, and roommate-style assignments are general matchings.
• Computational chemistry. Kekulé structures (assigning double bonds) are perfect matchings on the molecular graph.

Libraries expose it directly: NetworkX's max_weight_matching, LEMON, Boost Graph, and Vladimir Kolmogorov's Blossom V for the min-cost perfect-matching variant used across computer vision and OR.

Blossom vs. its cousins: the tradeoff

The natural comparison is against bipartite matching algorithms and the flow-based approach:

• vs. Hopcroft-Karp (O(E·√V)): Hopcroft-Karp is faster and far simpler to implement, but it is only correct on bipartite graphs. On a graph with any odd cycle it silently undercounts. Blossom's entire reason to exist is handling those odd cycles — you pay implementation complexity for correctness on general graphs.
• vs. max-flow reductions: Bipartite matching reduces cleanly to max-flow, but there is no such clean flow reduction for general matching — the odd-set constraints in Edmonds' matching polytope have no unit-capacity flow analog. This is precisely why a bespoke algorithm was needed.
• vs. Micali-Vazirani: MV is asymptotically best at O(E·√V) but notoriously hard to implement correctly; its full proof took Vazirani decades. Most practitioners use the O(V^3) blossom-with-labeling because it is simpler and fast enough.

Rule of thumb: bipartite → Hopcroft-Karp; general and correctness-critical → blossom; huge general graphs where every factor matters → MV.

Pitfalls, failure modes, and significance

Failure modes. The classic bug is running a bipartite augmenting search on a graph you assumed was bipartite but that contains an odd cycle — you get a plausible-looking but non-maximum matching with no error thrown. Implementation pitfalls specific to blossoms: (1) getting the blossom base (lowest common ancestor of the two even vertices) wrong, which corrupts the lift; (2) botching path lifting so the recovered augmenting path re-uses a vertex; (3) forgetting that blossoms can nest, so contraction must be recursive.

• Always confirm whether your graph is bipartite first — if so, use the simpler, faster algorithm.
• For weighted matching, use the primal-dual (Hungarian-style) blossom algorithm; the cardinality version does not respect edge weights.

Significance. Beyond the algorithm, Edmonds' 1965 paper argued that polynomial time is the right definition of "efficient," seeding the theory of P vs. NP and the matching polytope. It remains one of the deepest positive results in algorithm design: a genuinely hard combinatorial obstacle (odd cycles) tamed by a single elegant idea (contract and lift).

Maximum-matching algorithms: bipartite vs. general graphs and their bounds

Algorithm	Graph class	Time complexity	Note
Augmenting BFS/DFS	Bipartite	O(V·E)	Fails on odd cycles
Hopcroft-Karp	Bipartite	O(E·√V)	Phased augmenting paths
Edmonds' Blossom (original)	General	O(V^4)	First polynomial-time result, 1965
Blossom + labeling (Gabow)	General	O(V^3)	No explicit shrink; practical default
Micali-Vazirani	General	O(E·√V)	Best known; hard correctness proof
Blossom V (Kolmogorov)	General (weighted)	O(V^3) practical	State-of-the-art min-cost implementation