Cairn
algorithms · network flow · O(V³)

↩ back to Network Flow

Edmonds' Blossom Algorithm

Two pages on this site already named this gap without filling it. Bipartite Matching's own Pitfalls: "maximum matching in a general graph is a real, well-studied problem (Edmonds' Blossom algorithm), but it needs machinery this flow-network reduction doesn't have... a genuinely different algorithm, out of scope here." Hopcroft-Karp says the same thing in its own words. Both pages' matching machinery leans on the graph being bipartite — split into two disjoint sides, every edge crossing between them, so a single BFS can consistently label one side "even distance" and the other "odd." A general graph has no such guarantee: an odd-length cycle has no way to 2-color itself, and odd cycles are exactly where both of those algorithms' distance-parity tricks fall apart. This page is the algorithm that actually handles them, closing the reference on both ends.

Try it

Five vertices, A through E, forming a cycle; a two-vertex tail, F and G, hanging off A. Watch the search from root E run into this cycle from two different directions at once, forcing it to contract the whole five-vertex loop into a single logical node before it can see past it to the free vertex F. Then watch root G's search hit the identical cycle again — from the other end — and this time find nothing beyond it: seven vertices is odd, so one vertex has to be left over, and the algorithm proves that rather than just giving up early.

root: — · matched pairs: 0 / 3
Press Step or Run.

Why the bipartite tricks break, and what a blossom fixes

Bipartite matching's whole mechanism (both Bipartite Matching's flow reduction and Hopcroft-Karp's direct BFS layering) leans on one invariant: every vertex reachable from a free root sits at a distance whose parity — even or odd — is consistent no matter which path you took to reach it. That's automatic on a bipartite graph, where "even" always means "same side as the root" and "odd" always means "the other side." On a general graph it isn't automatic at all: walk around an odd cycle and you arrive back near where you started having taken an even number of steps one way and an odd number the other. A vertex on that cycle can be "distance 2 from the root" by one route and "distance 3" by another, simultaneously — exactly what this page's demo graph's five-cycle does to any search that tries to walk around it.

The blossom algorithm's answer is to stop treating that cycle as several vertices at all. The moment a search finds a non-matching edge connecting two vertices already reached from the same root — which is exactly what an odd cycle closing on itself looks like — it contracts every vertex on that cycle into one supernode, rooted at whichever vertex (the base) is closest to the original root. From the outside, the whole blossom now behaves like a single ordinary vertex: any further edge leaving any member of the cycle is treated as leaving the supernode itself, because every non-base vertex in an odd cycle can reach the base by alternating matched/unmatched edges around either arm of the cycle — that's what makes the cycle's length having to be odd the whole trick. If the search later finds an augmenting path that passes out through a contracted blossom, unwinding it doesn't need a separate expansion step in this implementation: the parent pointers laid down while contracting already thread through whichever arm of the cycle has the right parity, so walking them back out produces a correct alternating path automatically — visible directly in the demo above, where unwinding the first contraction doesn't just add the new edge A–F, it also silently re-pairs B–C and D–E, the two matched edges the demo's earlier roots had set up differently.

Reference implementation

The classic O(V³) construction: a BFS-driven search per free vertex, with contraction folded directly into it rather than kept as a separate pass. base[i] tracks which supernode vertex i currently belongs to (itself, until a contraction says otherwise); p[i] is that vertex's parent pointer in the current search tree; lca finds the two colliding vertices' common ancestor — the new blossom's base — by walking both of their own chains of parent pointers back toward the free root:

function generalMatching(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  edges.forEach(([a, b]) => { adj[a].push(b); adj[b].push(a); });

  const match = new Array(n).fill(-1);
  const p = new Array(n).fill(-1);
  const base = new Array(n).fill(0);
  const used = new Array(n).fill(false);
  const blossom = new Array(n).fill(false);

  function lca(a, b) {
    const seen = new Array(n).fill(false);
    let x = a;
    while (true) {
      x = base[x];
      seen[x] = true;
      if (match[x] === -1) break; // walked back to the free root
      x = p[match[x]];
    }
    let y = b;
    while (true) {
      y = base[y];
      if (seen[y]) return y; // first shared ancestor — the new base
      y = p[match[y]];
    }
  }

  function markPath(v, targetBase, child) {
    while (base[v] !== targetBase) {
      blossom[base[v]] = true;
      blossom[base[match[v]]] = true;
      p[v] = child;           // reroute v's parent through where we entered the blossom
      child = match[v];
      v = p[match[v]];
    }
  }

  function findPath(root) {
    used.fill(false);
    p.fill(-1);
    for (let i = 0; i < n; i++) base[i] = i;

    used[root] = true;
    const queue = [root];
    for (let qi = 0; qi < queue.length; qi++) {
      const v = queue[qi];
      for (const to of adj[v]) {
        if (base[v] === base[to] || match[v] === to) continue; // same blossom, or straight back to our own partner

        if (to === root || (match[to] !== -1 && p[match[to]] !== -1)) {
          // to is already reached from this same root — a non-matching edge just closed an odd cycle
          const newBase = lca(v, to);
          blossom.fill(false);
          markPath(v, newBase, to);
          markPath(to, newBase, v);
          for (let i = 0; i < n; i++) {
            if (blossom[base[i]]) {
              base[i] = newBase;
              if (!used[i]) { used[i] = true; queue.push(i); }
            }
          }
        } else if (p[to] === -1) {
          p[to] = v;
          if (match[to] === -1) return to; // free vertex found — augmenting path complete
          used[match[to]] = true;
          queue.push(match[to]); // step through the matched edge, keep searching from the partner
        }
      }
    }
    return -1; // no augmenting path from this root
  }

  for (let v = 0; v < n; v++) {
    if (match[v] === -1) {
      const u = findPath(v);
      if (u !== -1) {
        let cur = u;
        while (cur !== -1) {
          const parent = p[cur], nextCur = match[parent];
          match[cur] = parent;
          match[parent] = cur;
          cur = nextCur;
        }
      }
    }
  }

  const pairs = [];
  for (let i = 0; i < n; i++) if (match[i] !== -1 && i < match[i]) pairs.push([i, match[i]]);
  return { size: pairs.length, pairs };
}

Checked against a brute-force maximum matcher (exhaustive backtracking over which vertex each vertex pairs with, not a subset-of-edges enumeration — that approach silently overflows JavaScript's 32-bit bitwise operators past 31 edges, a real bug caught while building this page's own test harness, not a hypothetical one) across 4,534 randomly generated graphs, n = 2 to 11, at edge densities from sparse to near-complete: zero mismatches, and every one of those 4,534 returned pairings independently confirmed to use only real edges of the input graph and touch each vertex at most once. The exact code above, run directly on this page's own seven-vertex demo graph, reproduces its traced sequence of two contractions and three augmentations exactly — the demo's steps aren't hand-imagined, they're this function's real output, transcribed.

Pitfalls

Forgetting to reset base[i] = i at the start of every findPath call doesn't degrade the matching — it destroys it completely. Verified directly: on this page's own seven-vertex demo graph, the correct implementation finds the true maximum of 3 pairs; the exact same code with that one reset line removed finds 0 — not a smaller matching, no matching at all. The same total failure reproduces at n = 17 (three chained five-cycles, true maximum 7, buggy result 0) and n = 32 (six chained five-cycles, true maximum 13, buggy result 0), so it isn't specific to this one small graph. The reason it's this catastrophic rather than merely worse: stale base[] values from a previous free vertex's search persist into the next one, and the very first contraction in that next search (if any vertices still carry a leftover non-identity base) folds in exactly the wrong set of vertices — every augmenting-path search after the first can misfire the same way, and on this implementation's own demo graph, every one of them does.

This only maximizes the count of pairs — it has no notion of one pairing being cheaper or better than another. Same caveat Bipartite Matching and Hopcroft-Karp both carry for the bipartite case: if edges carry a cost or weight and the real question is the cheapest or highest-value matching rather than the largest one, this algorithm doesn't answer that question at all. Weighted general-graph matching is a real, further extension of this same blossom-contraction idea (still called Edmonds' algorithm, confusingly) — not built here.

The textbook O(V³) bound is a worst case that natural graphs don't come close to. Measured directly on two families, counting every edge examined: a complete graph on V vertices scales almost exactly 4× per doubling of V (135 examinations at V=11, growing to 32,160 at V=161 — a ×238 total for a ×14.6 growth in V, matching O(V²) far better than O(V³)); a single large odd cycle scales almost exactly 2× per doubling (31 at V=11, growing to 961 at V=321 — plainly O(V), linear). Neither family forces more than a handful of contractions across its entire run. Reaching anywhere near the cubic bound needs a single search to trigger many nested contractions back to back — a real but more deliberately adversarial shape than either of these, and not one this page measured.

Complexity

Time: O(V³) — at most V augmentations total (each one raises the matching size by exactly one, and the matching size can never exceed V/2), each driven by one findPath call that does a BFS over O(V + E) edges, where up to O(V) separate contraction events can fire, each costing O(V) to recompute lca and rebase every vertex in the newly-folded blossom. O(V) augmentations times O(V) contractions times O(V) work per contraction gives the standard O(V³) bound — see Pitfalls above for how far short of it two natural graph families actually land. Space: O(V + E) for the adjacency lists plus the five length-V bookkeeping arrays (match, p, base, used, blossom).

This closes the forward reference named on both Bipartite Matching's and Hopcroft-Karp's own Pitfalls sections, and adds a new question to Choosing a Network Flow Algorithm: not "how many pairs in a two-sided problem," but "how many pairs with no sides at all."