The Matching Arrives in Waves

A matching is a set of edges that do not share endpoints.

That definition is modest enough to hide the algorithmic drama. In a bipartite graph, the left side might be workers and the right side jobs, or tests and machines, or pending tasks and available slots. The maximum-cardinality question does not ask whether the assignment is stable, weighted, fair, or human-readable. It asks one clean thing:

how many disjoint pairs can this graph support?

The basic repair operation is an augmenting path. Start at an unmatched left vertex. Walk across an unmatched edge, then a matched edge, then an unmatched edge, alternating until you end at an unmatched right vertex.

If the path is:

free left -- unmatched -- right -- matched -- left -- unmatched -- free right

then flip every edge on it:

unmatched edges become matched
matched edges become unmatched

The endpoints become matched, and every interior vertex stays matched. The matching grows by one.

Berge’s theorem gives the certificate: a matching is maximum if and only if no augmenting path exists.¹ So a simple algorithm is already available: keep finding any augmenting path and flipping it.

Hopcroft-Karp asks a sharper question:

why flip one path when the current shortest layer contains many disjoint ones?

The Alternating Forest Is A Search Index

Given a current matching \(M\), orient the search by parity:

from a free left vertex, cross unmatched edges to the right side;
from a reached right vertex that is already matched, cross its matched edge back to the left side;
stop when a free right vertex is reached.

This is not an ordinary BFS over the graph. It is a BFS over the alternating structure induced by the current matching.

The BFS distances live on left vertices. Distance 0 is every free left vertex. From a left vertex at distance \(d\), an unmatched edge can reveal a right vertex. If that right vertex is matched, its mate becomes a left vertex at distance \(d+1\). If the right vertex is free, a shortest augmenting path has been found.

Hopcroft-Karp then runs DFS only inside this layered alternating graph and finds a maximal set of vertex-disjoint shortest augmenting paths. All of those paths can be flipped at once because they do not touch the same vertices.

That is the wave:

BFS:  expose the current shortest augmenting layer
DFS:  pack disjoint augmenting paths inside that layer
flip: grow the matching by all packed paths
repeat

Hopcroft and Karp’s original paper proves an \(O((m+n)\sqrt n)\) time bound for a bipartite graph with \(n\) vertices and \(m\) edges.² The important structural claim is not just “BFS plus DFS.” It is that after enough shortest augmenting paths are exhausted, the shortest possible augmenting path gets longer, and that can happen only a controlled number of times.

Why Shortest Paths Matter

If you find one augmenting path at a time, an unlucky path can leave many other easy repairs for later. That still converges, but it may spend one full search per unit of matching growth.

Hopcroft-Karp refuses to leave the current depth half-used. Once the BFS has identified the shortest augmenting distance, the DFS phase tries to saturate that layer with vertex-disjoint repairs. It does not chase longer paths yet.

This gives two useful invariants:

within a phase, all augmenting paths have minimum length
between phases, the next successful path length strictly increases

The proof of the full bound is more delicate than those two lines, but the engineering intuition is already visible: the algorithm amortizes search over a batch of equally urgent repairs.

The Browser Lab

The lab below runs Hopcroft-Karp, a one-path-at-a-time DFS baseline, a brute force maximum-matching oracle, and the standard alternating-reachability vertex cover certificate. Green edges are matched. Orange edges are augmenting paths in the selected phase. Blue dashed edges show the alternating BFS layer. Purple nodes form the final cover certificate.

Graph two chain traps Phase 0 / 0

left0

right0

edges0

matching0

HK phases0

single-path flips0

cover size0

auditpasses

The terminal phase has no augmenting path. Its alternating reachability set gives the vertex-cover certificate drawn in purple.

In the default graph, the maximum matching has 6 edges. A one-path-at-a-time baseline performs 6 flips. Hopcroft-Karp still flips 6 augmenting paths total, but it batches them into 2 successful phases:

phase 0: four length-1 repairs
phase 1: two longer repairs exposed by the new alternating forest

Then the terminal phase finds no augmenting path. The purple vertex cover has size 6, matching the 6-edge matching.

That cover is not decoration. In a bipartite graph, the alternating-reachability construction from a maximum matching gives a minimum vertex cover; Kőnig’s theorem says the two cardinalities are equal.³ The lab also checks the answer by brute force on these small graphs, so the visual certificate is not trusted blindly.

Reproducibility Check

The browser file is also a CommonJS module. From the repository root:

node - <<'NODE'
const lab = require("./assets/js/hopcroft-karp-lab.js");
const EXPECTED_NAMED_SHAPE = [
  "traps:two chain traps:left=6:right=6:edges=10:matching=6:brute=6:phases=2:paths=4+2:cover=6:single=6:checks=21/21",
  "applicants:applicant shortlist:left=7:right=7:edges=17:matching=7:brute=7:phases=1:paths=7:cover=7:single=7:checks=18/18",
  "bottleneck:shared bottleneck:left=8:right=6:edges=16:matching=6:brute=6:phases=1:paths=6:cover=6:single=6:checks=17/17",
  "grid:staggered grid:left=8:right=8:edges=19:matching=8:brute=8:phases=1:paths=8:cover=8:single=8:checks=19/19"
];
const EXPECTED_PHASE_SHAPE = [
  "phases=1:cases=3:passed=3:graphs=applicants, bottleneck, grid:maxMatching=8",
  "phases=2:cases=1:passed=1:graphs=traps:maxMatching=6"
];
const EXPECTED_NAMED_CHECK_SHAPE = [
  "traps:Hopcroft-Karp matching is valid|single-path matching is valid|Hopcroft-Karp size equals brute force|single-path size equals brute force|alternating cover hits every edge|cover size equals matching size|phase 0 has a BFS augmenting layer|phase 0 finds at least one path|phase 0 paths are vertex-disjoint|phase 0 path 0 is augmenting|phase 0 path 1 is augmenting|phase 0 path 2 is augmenting|phase 0 path 3 is augmenting|phase 0 matching delta equals path count|phase 1 has a BFS augmenting layer|phase 1 finds at least one path|phase 1 paths are vertex-disjoint|phase 1 path 0 is augmenting|phase 1 path 1 is augmenting|phase 1 matching delta equals path count|phase 2 matching delta equals path count",
  "applicants:Hopcroft-Karp matching is valid|single-path matching is valid|Hopcroft-Karp size equals brute force|single-path size equals brute force|alternating cover hits every edge|cover size equals matching size|phase 0 has a BFS augmenting layer|phase 0 finds at least one path|phase 0 paths are vertex-disjoint|phase 0 path 0 is augmenting|phase 0 path 1 is augmenting|phase 0 path 2 is augmenting|phase 0 path 3 is augmenting|phase 0 path 4 is augmenting|phase 0 path 5 is augmenting|phase 0 path 6 is augmenting|phase 0 matching delta equals path count|phase 1 matching delta equals path count",
  "bottleneck:Hopcroft-Karp matching is valid|single-path matching is valid|Hopcroft-Karp size equals brute force|single-path size equals brute force|alternating cover hits every edge|cover size equals matching size|phase 0 has a BFS augmenting layer|phase 0 finds at least one path|phase 0 paths are vertex-disjoint|phase 0 path 0 is augmenting|phase 0 path 1 is augmenting|phase 0 path 2 is augmenting|phase 0 path 3 is augmenting|phase 0 path 4 is augmenting|phase 0 path 5 is augmenting|phase 0 matching delta equals path count|phase 1 matching delta equals path count",
  "grid:Hopcroft-Karp matching is valid|single-path matching is valid|Hopcroft-Karp size equals brute force|single-path size equals brute force|alternating cover hits every edge|cover size equals matching size|phase 0 has a BFS augmenting layer|phase 0 finds at least one path|phase 0 paths are vertex-disjoint|phase 0 path 0 is augmenting|phase 0 path 1 is augmenting|phase 0 path 2 is augmenting|phase 0 path 3 is augmenting|phase 0 path 4 is augmenting|phase 0 path 5 is augmenting|phase 0 path 6 is augmenting|phase 0 path 7 is augmenting|phase 0 matching delta equals path count|phase 1 matching delta equals path count"
];
const EXPECTED_GROUPS = EXPECTED_NAMED_SHAPE.length + 1;
const EXPECTED_NAMED_CASES = EXPECTED_NAMED_SHAPE.length;
const EXPECTED_EXHAUSTIVE_CASES = 74954;
const EXPECTED_EXHAUSTIVE_CHECKS = 1174257;
const EXPECTED_CHECKS = 1174332;

function sameList(actual, expected) {
  return actual.length === expected.length &&
    actual.every((value, index) => value === expected[index]);
}

function namedShape(row) {
  return `${row.example}:${row.label}:left=${row.left}:right=${row.right}:` +
    `edges=${row.edges}:matching=${row.matching}:brute=${row.bruteForceSize}:` +
    `phases=${row.phases}:paths=${row.phasePathCounts}:cover=${row.coverSize}:` +
    `single=${row.singlePathAugmentations}:` +
    `checks=${row.passedChecks}/${row.totalChecks}`;
}

function phaseShape(row) {
  return `phases=${row.phases}:cases=${row.cases}:passed=${row.passed}:` +
    `graphs=${row.graphs}:maxMatching=${row.maxMatching}`;
}

function namedCheckShape(row) {
  const state = lab.evaluate({ example: row.example });
  return `${row.example}:${state.audit.checks.map((check) => check.name).join("|")}`;
}

const audit = lab.auditHopcroftKarp();
console.table(audit.byPhaseCount);
const shape = {
  exhaustive: {
    checked: audit.exhaustive.checked,
    failed: audit.exhaustive.failedChecks.length,
    passed: audit.exhaustive.passed,
    passedChecks: audit.exhaustive.passedChecks,
    totalChecks: audit.exhaustive.totalChecks
  },
  named: audit.cases.map(namedShape),
  namedChecks: audit.cases.map(namedCheckShape),
  phaseGroups: audit.byPhaseCount.map(phaseShape)
};
const shapeErrors = [];
if (!sameList(shape.named, EXPECTED_NAMED_SHAPE)) {
  shapeErrors.push({ name: "named", actual: shape.named, expected: EXPECTED_NAMED_SHAPE });
}
if (!sameList(shape.phaseGroups, EXPECTED_PHASE_SHAPE)) {
  shapeErrors.push({
    name: "phaseGroups",
    actual: shape.phaseGroups,
    expected: EXPECTED_PHASE_SHAPE
  });
}
if (!sameList(shape.namedChecks, EXPECTED_NAMED_CHECK_SHAPE)) {
  shapeErrors.push({
    name: "namedChecks",
    actual: shape.namedChecks,
    expected: EXPECTED_NAMED_CHECK_SHAPE
  });
}
if (shape.exhaustive.checked !== EXPECTED_EXHAUSTIVE_CASES ||
    shape.exhaustive.totalChecks !== EXPECTED_EXHAUSTIVE_CHECKS ||
    shape.exhaustive.failed !== 0 ||
    !shape.exhaustive.passed) {
  shapeErrors.push({
    name: "exhaustive",
    actual: shape.exhaustive,
    expected: {
      checked: EXPECTED_EXHAUSTIVE_CASES,
      failed: 0,
      passed: true,
      totalChecks: EXPECTED_EXHAUSTIVE_CHECKS
    }
  });
}

const failedCases = audit.cases.filter(
  (row) => !row.passed || row.passedChecks !== row.totalChecks
);
const exhaustiveFailures = audit.exhaustive.failedChecks.slice(0, 10);
if (shapeErrors.length ||
    !audit.ok ||
    audit.cases.length !== EXPECTED_NAMED_CASES ||
    audit.exhaustiveCases !== EXPECTED_EXHAUSTIVE_CASES ||
    audit.total !== EXPECTED_GROUPS ||
    audit.totalChecks !== EXPECTED_CHECKS ||
    failedCases.length ||
    !audit.exhaustive.passed ||
    audit.passed !== audit.total || audit.passedChecks !== audit.totalChecks) {
  throw new Error(JSON.stringify({
    shapeErrors,
    failures: audit.failures,
    issues: audit.issues.slice(0, 10),
    failedCases,
    exhaustiveFailures,
    totals: {
      exhaustiveCases: audit.exhaustiveCases,
      namedRows: audit.cases.length,
      passed: audit.passed,
      passedChecks: audit.passedChecks,
      total: audit.total,
      totalChecks: audit.totalChecks
    }
  }, null, 2));
}
console.log(audit.exhaustiveCases + " exhaustive bipartite graphs checked");
console.table(audit.cases.map((row) => ({
  graph: row.label,
  matching: row.matching,
  brute: row.bruteForceSize,
  phases: row.phases,
  paths: row.phasePathCounts,
  cover: row.coverSize,
  passed: row.passed
})));
console.log(`${audit.passed}/${audit.total} audit groups and ` +
  `${audit.passedChecks}/${audit.totalChecks} checks passed`);
NODE

The current audit checks the four named graph scenarios and every bipartite graph with 1 to 4 left vertices and 1 to 4 right vertices. That is 74,954 exhaustive small graphs and 1,174,332 named checks. For each case it verifies:

Hopcroft-Karp returns a valid matching;
the one-path DFS baseline returns a valid matching;
both matching sizes equal a brute-force maximum-matching oracle;
every phase path is a real augmenting path relative to that phase’s incoming matching;
paths batched in one phase are vertex-disjoint;
the matching size increases by the number of phase paths; and
the final alternating-reachability vertex cover covers every edge and has size equal to the matching.

The implementation is deliberately small: assets/js/hopcroft-karp-lab.js.

Where The Model Stops

This is maximum-cardinality bipartite matching. It is not stable matching and it is not weighted assignment.

Stable matching asks whether any pair would rather leave their assigned partners for each other. Maximum matching ignores preferences entirely. Weighted assignment asks for the best total weight, usually with the Hungarian algorithm or min-cost flow. Hopcroft-Karp ignores weights entirely.

Those distinctions matter in product systems. A scheduler that merely maximizes the number of filled slots may create bad allocations. A market design that merely avoids blocking pairs may leave cardinality or welfare on the table. A weighted assignment solver may be the wrong tool if the graph is huge, sparse, and the first requirement is simply “match as many as possible.”

Hopcroft-Karp earns its place when the contract is exactly:

bipartite graph in
maximum number of disjoint edges out

Under that contract, the wave idea is precise. Do not repair one complaint and restart. Find the shortest complaints, pack all disjoint ones, flip them together, and only then ask whether the next complaint must be longer.

The matching grows because every augmenting path is local evidence. It arrives in waves because the algorithm refuses to waste a shortest layer.

Claude Berge, “Two Theorems in Graph Theory”, Proceedings of the National Academy of Sciences 43(9):842-844, 1957. PubMed record: https://pubmed.ncbi.nlm.nih.gov/16590096/. ↩
John E. Hopcroft and Richard M. Karp, “An \(n^{5/2}\) Algorithm for Maximum Matchings in Bipartite Graphs”, SIAM Journal on Computing 2(4):225-231, 1973. A PDF copy is hosted by the University of Michigan: https://web.eecs.umich.edu/~pettie/matching/Hopcroft-Karp-bipartite-matching.pdf. ↩
The vertex-cover certificate used in the lab is the standard constructive form of Kőnig’s theorem for bipartite graphs. See, for example, Princeton ORF 523 notes, “Bipartite matching and vertex covers”. ↩

The Alternating Forest Is A Search Index

Why Shortest Paths Matter

The Browser Lab

Reproducibility Check

Where The Model Stops

Related notes