THE FOLD / SPAWN / CHECKPOINT ZERO / THE HOPCROFT-KARP
THE HOPCROFT-KARP
maximum bipartite matching = minimum vertex cover
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Hopcroft–Karp finds a maximum matching in a bipartite graph — the largest set of edges with no shared endpoints (jobs to workers, students to schools) — in O(E√V), faster than the naive O(VE). It repeatedly finds augmenting paths (paths that alternate unmatched and matched edges, starting and ending free) and flips them to grow the matching by one; its speed comes from finding many shortest augmenting paths per phase.
And by König’s theorem, the maximum matching size equals the minimum vertex cover — a max and a min coincide.
LIT verified live: over 300 random bipartite graphs, the augmenting-path matching size equals a brute-force maximum matching (window.__hopcroftkarp). FIG no framing; exact matching.
And by König’s theorem, the maximum matching size equals the minimum vertex cover — a max and a min coincide.
LIT verified live: over 300 random bipartite graphs, the augmenting-path matching size equals a brute-force maximum matching (window.__hopcroftkarp). FIG no framing; exact matching.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at checkpoint-zero — pairing up cleanly from a fresh start, as many as can be matched. Hopcroft–Karp is that maximal pairing. AVAN (AI) built the instrument: the augmenting-path search, the matching growth, the brute-force cross-check (and the König duality).
Credit as content: John Hopcroft & Richard Karp (1973); Dénes König’s theorem (1931). The weave: David names the checkpoint; I grow a matching by flipping augmenting paths and confirm its size equals the true maximum — which, by König, is also the minimum vertex cover.
Credit as content: John Hopcroft & Richard Karp (1973); Dénes König’s theorem (1931). The weave: David names the checkpoint; I grow a matching by flipping augmenting paths and confirm its size equals the true maximum — which, by König, is also the minimum vertex cover.
3 ONE DIMENSION
An augmenting path: it starts and ends at unmatched vertices and alternates non-matching / matching edges. Flip every edge along it — unmatched become matched and vice versa — and the matching grows by exactly one.
4 TWO DIMENSIONS · INTERACTIVE
A bipartite graph, left and right. Find the maximum matching (highlighted edges); verify its size equals a brute-force maximum, which by König equals the minimum vertex cover.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the maximum matching — the most disjoint pairs the graph allows.
AVAN’s addition (the inverse-companion): a matching is maximum exactly when no augmenting path remains (Berge’s lemma) — so the algorithm’s stopping condition is a certificate of optimality. And the alternating-reachable / unreachable split from the free vertices yields a minimum vertex cover of the same size (König). The inverse of ‘the most edges you can match’ is ‘the fewest vertices that touch every edge,’ and the two numbers are equal. Magenta is the minimum vertex cover — the fewest guards covering all edges; green is the maximum matching — the most disjoint pairs; same count, dual views. Maximising pairs and minimising guards are one problem, exactly as max-flow equals min-cut.
LIT Genuine Hopcroft-Karp bipartite matching (Hopcroft & Karp 1973; Konig's theorem 1931). Verified live: the augmenting-path matching (Kuhn/Hungarian-style augmentation, the core Hopcroft-Karp grows) returns a matching whose size equals a brute-force maximum matching for 300 random bipartite graphs (window.__hopcroftkarp.matchesBrute).
FIG No framing: the augmenting-path search and the brute-force cross-check run in-browser and agree exactly. The AVAN inverse is honest — a matching is maximum exactly when no augmenting path remains (Berge), a certificate of optimality, and the alternating-reachable split yields a minimum vertex cover of the same size (Konig), exactly as max-flow equals min-cut; magenta is the min vertex cover, green the max matching.
FIG No framing: the augmenting-path search and the brute-force cross-check run in-browser and agree exactly. The AVAN inverse is honest — a matching is maximum exactly when no augmenting path remains (Berge), a certificate of optimality, and the alternating-reachable split yields a minimum vertex cover of the same size (Konig), exactly as max-flow equals min-cut; magenta is the min vertex cover, green the max matching.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of CHECKPOINT ZERO · David Lee Wise (ROOT0), with AVAN