Chapter 13
Matching
Matching is where duality becomes visible: every max matching has a min vertex cover, and the proof of one is an algorithm for the other.
7 pages6,048 words14 problems1 interactive
1Matching: Definitions and DualityMatchings, covers, and independent sets on one page — plus the two theorems that turn searching into proving.2Bipartite Matching (Kuhn's Algorithm)Augmenting paths by DFS, ten lines long, O(VE) — with the tie-breaking trick that makes it pass in practice.3Hopcroft–KarpAugment along a maximal set of shortest disjoint paths per phase, and the O(E sqrt V) bound falls out of two counting arguments.4Kőnig's Theorem and Minimum CoversOne alternating DFS gives the minimum vertex cover, the maximum independent set, and — with a small twist — the minimum path cover of a DAG.5The Hungarian AlgorithmWeighted assignment in O(n^3) with labels and equality subgraphs — the min-cost flow specialisation that is shorter, faster, and needs no graph.6Matching ApplicationsDomino tilings, rook placements, DAG path covers, poset width, and "maximum non-attacking set" — five reductions, one algorithm.7General Matching and BlossomsWhy odd cycles break the bipartite algorithm, what a blossom is, Edmonds' contraction, and the Tutte/Berge formulas.