Algorithm Deep Dive: Blossom Algorithm

A Bit of History

Jack Edmonds published "Paths, Trees, and Flowers" in 1965, introducing the Blossom Algorithm to solve maximum matching in general graphs — those that need not be bipartite, extending the theory from Part 16 and the Hopcroft-Karp deep dive, both of which apply only to the bipartite case. The paper is doubly historic: beyond the algorithm itself, Edmonds used it to informally articulate what "efficient algorithm" should mean — polynomial-time computability — a conceptual cornerstone that helped shape the entire later field of computational complexity theory, including the eventual formal definitions of the classes P and NP.

Working Principle

Bipartite matching algorithms rely on augmenting paths (Berge's theorem, Part 16): if you can find a path alternating between non-matching and matching edges that starts and ends at unmatched vertices, flipping it grows the matching by one. This works flawlessly in bipartite graphs — but in general graphs, an odd-length cycle (a "blossom") can trap the augmenting-path search in a way that has no valid resolution using the naive bipartite technique.

Edmonds' insight: whenever the search encounters a blossom (an odd cycle reached via alternating paths from two different directions), contract the entire blossom down to a single "super-vertex," continue the augmenting-path search on this smaller contracted graph, and — if an augmenting path is found — expand the blossom back out afterward, carefully routing the path through the correct side of the original cycle.

Key Insight

A blossom, once contracted, behaves exactly like a single unmatched vertex for the purposes of the search — this is the deep structural fact that makes the contraction valid rather than just a convenient hack. It guarantees that any augmenting path found in the contracted graph corresponds to a genuine augmenting path in the original graph once the blossom is expanded back out.

Worked Example

Consider a 5-vertex graph: a triangle $A\text{-}B\text{-}C$ (an odd cycle) with $C$ additionally connected to $D$, and $D$ connected to $E$. Suppose $A\text{-}B$ is currently matched, and $D\text{-}E$ is matched, leaving $C$ unmatched. An augmenting-path search from $C$ reaches the triangle $A\text{-}B\text{-}C$ — a blossom — since $C$ can reach both $A$ and $B$ via alternating paths. Contracting $\{A,B,C\}$ into a single super-vertex $S$, the graph simplifies to $S\text{-}D\text{-}E$, where $D\text{-}E$ is matched and $S$ is unmatched — an ordinary augmenting path $S \to D \to E$ is immediately visible. Expanding $S$ back out and routing the path correctly through the triangle (say, via $C \to A$ or $C \to B$, whichever preserves a valid alternating structure) produces a genuine augmenting path in the original graph, growing the matching by one.

Correctness

The correctness argument rests on proving the blossom-contraction step is sound: an augmenting path exists in the original graph if and only if one exists in the graph with the blossom contracted. This equivalence follows because every vertex in a blossom can always be matched to any single "entry point" into the blossom via an alternating path within the cycle itself — so treating the whole blossom as one flexible unmatched-or-matched unit loses no essential information about whether augmentation is possible, while dramatically simplifying the search.

Complexity Analysis

Edmonds' original 1965 algorithm ran in $O(V^4)$. Later refinements improved this substantially — most notably Silvio Micali and Vijay Vazirani's 1980 algorithm, which achieves the same $O(E\sqrt{V})$ bound as Hopcroft-Karp's bipartite-only algorithm, by generalizing that algorithm's phase-based approach to handle blossom contraction:

$$\text{Time (Edmonds, 1965): } O(V^4) \qquad \text{Time (Micali-Vazirani, 1980): } O(E\sqrt{V})$$

The Micali-Vazirani bound is notoriously intricate to implement correctly — its correctness proof itself remained incompletely documented for decades, with a fully rigorous, modern proof only published in 2012 by Vazirani, nearly 30 years after the original algorithm.

Implementation

from collections import deque

def blossom_max_matching(n, edges):
    """
    Simplified O(V^3) blossom algorithm for general graph maximum matching.
    n: number of vertices (0-indexed). edges: list of (u, v) pairs.
    Returns match[] where match[v] is v's partner, or -1 if unmatched.
    """
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    match = [-1] * n
    p = [0] * n       # parent in the alternating tree
    base = [0] * n     # base (root of blossom) for each vertex
    used = [False] * n
    blossom = [False] * n

    def lca(a, b):
        used_path = [False] * n
        u = a
        while True:
            u = base[u]
            used_path[u] = True
            if match[u] == -1:
                break
            u = p[match[u]]
        v = b
        while not used_path[base[v]]:
            v = p[match[v]]
        return base[v]

    def mark_path(v, b, child):
        while base[v] != b:
            blossom[base[v]] = True
            blossom[base[match[v]]] = True
            p[v] = child
            child = match[v]
            v = p[match[v]]

    def find_path(root):
        nonlocal base
        used[:] = [False] * n
        p[:] = [-1] * n
        for i in range(n):
            base[i] = i
        used[root] = True
        q = deque([root])
        while q:
            v = q.popleft()
            for to in adj[v]:
                if base[v] == base[to] or match[v] == to:
                    continue
                if to == root or (match[to] != -1 and p[match[to]] != -1):
                    curbase = lca(v, to)
                    blossom[:] = [False] * n
                    mark_path(v, curbase, to)
                    mark_path(to, curbase, v)
                    for i in range(n):
                        if blossom[base[i]]:
                            base[i] = curbase
                            if not used[i]:
                                used[i] = True
                                q.append(i)
                elif p[to] == -1:
                    p[to] = v
                    if match[to] == -1:
                        return to
                    else:
                        used[match[to]] = True
                        q.append(match[to])
        return -1

    for v in range(n):
        if match[v] == -1:
            u = find_path(v)
            if u != -1:
                while u != -1:
                    pv, ppv = p[u], match[p[u]]
                    match[u] = p[u]
                    match[p[u]] = u
                    u = ppv

    return match

edges = [(0,1), (1,2), (2,0), (2,3), (3,4)]  # triangle 0-1-2 plus a tail 2-3-4
print(blossom_max_matching(5, edges))

// Simplified O(V^3) Blossom Algorithm (Edmonds' 1965 approach). Micali-Vazirani's
// O(E*sqrt(V)) refinement is considerably more intricate and is typically used
// only via well-tested libraries in production settings.
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

int n;
vector<vector<int>> adj;
vector<int> matchv, p, base;
vector<bool> used, blossomArr;

int lca(int a, int b) {
    vector<bool> usedPath(n, false);
    int u = a;
    while (true) {
        u = base[u];
        usedPath[u] = true;
        if (matchv[u] == -1) break;
        u = p[matchv[u]];
    }
    int v = b;
    while (!usedPath[base[v]]) v = p[matchv[v]];
    return base[v];
}

void markPath(int v, int b, int child) {
    while (base[v] != b) {
        blossomArr[base[v]] = true;
        blossomArr[base[matchv[v]]] = true;
        p[v] = child;
        child = matchv[v];
        v = p[matchv[v]];
    }
}

int findPath(int root) {
    fill(used.begin(), used.end(), false);
    fill(p.begin(), p.end(), -1);
    for (int i = 0; i < n; i++) base[i] = i;
    used[root] = true;
    queue<int> q;
    q.push(root);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        for (int to : adj[v]) {
            if (base[v] == base[to] || matchv[v] == to) continue;
            if (to == root || (matchv[to] != -1 && p[matchv[to]] != -1)) {
                int curbase = lca(v, to);
                fill(blossomArr.begin(), blossomArr.end(), false);
                markPath(v, curbase, to);
                markPath(to, curbase, v);
                for (int i = 0; i < n; i++) {
                    if (blossomArr[base[i]]) {
                        base[i] = curbase;
                        if (!used[i]) { used[i] = true; q.push(i); }
                    }
                }
            } else if (p[to] == -1) {
                p[to] = v;
                if (matchv[to] == -1) return to;
                used[matchv[to]] = true;
                q.push(matchv[to]);
            }
        }
    }
    return -1;
}

int main() {
    n = 5;
    adj.assign(n, {});
    vector<pair<int,int>> edges = {{0,1},{1,2},{2,0},{2,3},{3,4}};
    for (auto& e : edges) { adj[e.first].push_back(e.second); adj[e.second].push_back(e.first); }
    matchv.assign(n, -1); p.assign(n, -1); base.assign(n, 0);
    used.assign(n, false); blossomArr.assign(n, false);

    for (int v = 0; v < n; v++) {
        if (matchv[v] == -1) {
            int u = findPath(v);
            while (u != -1) {
                int pv = p[u], ppv = matchv[pv];
                matchv[u] = pv; matchv[pv] = u;
                u = ppv;
            }
        }
    }
    for (int v = 0; v < n; v++) cout << v << "->" << matchv[v] << " ";
    cout << endl;
    return 0;
}

// Simplified O(V^3) Blossom Algorithm (Edmonds' 1965 approach).
import java.util.*;

class Blossom {
    static int n;
    static List<List<Integer>> adj;
    static int[] matchv, p, base;
    static boolean[] used, blossomArr;

    static int lca(int a, int b) {
        boolean[] usedPath = new boolean[n];
        int u = a;
        while (true) {
            u = base[u];
            usedPath[u] = true;
            if (matchv[u] == -1) break;
            u = p[matchv[u]];
        }
        int v = b;
        while (!usedPath[base[v]]) v = p[matchv[v]];
        return base[v];
    }

    static void markPath(int v, int b, int child) {
        while (base[v] != b) {
            blossomArr[base[v]] = true;
            blossomArr[base[matchv[v]]] = true;
            p[v] = child;
            child = matchv[v];
            v = p[matchv[v]];
        }
    }

    static int findPath(int root) {
        Arrays.fill(used, false);
        Arrays.fill(p, -1);
        for (int i = 0; i < n; i++) base[i] = i;
        used[root] = true;
        Deque<Integer> q = new ArrayDeque<>();
        q.add(root);
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int to : adj.get(v)) {
                if (base[v] == base[to] || matchv[v] == to) continue;
                if (to == root || (matchv[to] != -1 && p[matchv[to]] != -1)) {
                    int curbase = lca(v, to);
                    Arrays.fill(blossomArr, false);
                    markPath(v, curbase, to);
                    markPath(to, curbase, v);
                    for (int i = 0; i < n; i++) {
                        if (blossomArr[base[i]]) {
                            base[i] = curbase;
                            if (!used[i]) { used[i] = true; q.add(i); }
                        }
                    }
                } else if (p[to] == -1) {
                    p[to] = v;
                    if (matchv[to] == -1) return to;
                    used[matchv[to]] = true;
                    q.add(matchv[to]);
                }
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        n = 5;
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        int[][] edges = {{0,1},{1,2},{2,0},{2,3},{3,4}};
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        matchv = new int[n]; p = new int[n]; base = new int[n];
        used = new boolean[n]; blossomArr = new boolean[n];
        Arrays.fill(matchv, -1);

        for (int v = 0; v < n; v++) {
            if (matchv[v] == -1) {
                int u = findPath(v);
                while (u != -1) {
                    int pv = p[u], ppv = matchv[pv];
                    matchv[u] = pv; matchv[pv] = u;
                    u = ppv;
                }
            }
        }
        for (int v = 0; v < n; v++) System.out.print(v + "->" + matchv[v] + " ");
    }
}

Real-World Applications

Case Study

Christofides' TSP Approximation

The Blossom Algorithm is not merely a theoretical curiosity — it is a required subroutine of the Christofides Algorithm deep dive earlier in this batch, which needs a minimum-weight perfect matching on an arbitrary (non-bipartite) set of odd-degree vertices from a spanning tree. Without a working general-graph matching algorithm, one of the most practically important TSP approximation guarantees in combinatorial optimization simply could not be computed.

TSP ApproximationCombinatorial Optimization

Exercises

Draw a small graph containing exactly one odd cycle (a triangle) and trace through the blossom-contraction step by hand as done in the worked example.
Explain in your own words why bipartite graphs never require blossom contraction at all — connect this to the fact that bipartite graphs contain no odd cycles.
Compare the Blossom Algorithm's role in this series to Hopcroft-Karp's: what specific graph-theoretic property (bipartite vs. general) determines which one applies?
Challenge: Research why the Micali-Vazirani algorithm's correctness proof took nearly 30 years to be fully rigorously documented, and summarize what made the original 1980 argument difficult to formally verify.

Limitations

Notoriously Complex to Implement

Even the simplified $O(V^3)$-style implementation shown here is considerably more intricate than any bipartite matching algorithm in this series, and the fastest known $O(E\sqrt{V})$ Micali-Vazirani version is widely regarded as one of the most difficult-to-implement-correctly algorithms in classical graph theory — in production settings, most engineers rely on well-tested libraries (like NetworkX's or LEMON's matching implementations) rather than writing blossom contraction logic from scratch.

Cookie Consent

Blossom Algorithm

Contents

A Bit of History

Working Principle

Key Insight

Worked Example

Correctness

Complexity Analysis

Implementation

Real-World Applications

Christofides' TSP Approximation

Exercises

Limitations

Notoriously Complex to Implement

Cookie Consent

Blossom Algorithm

Contents

A Bit of History

Working Principle

Key Insight

Worked Example

Correctness

Complexity Analysis

Implementation

Real-World Applications

Christofides' TSP Approximation

Exercises

Limitations

Notoriously Complex to Implement

Related Deep Dives

Graph Theory Series

Part 16: Matching Theory

Hopcroft-Karp Algorithm