Chapter 13 · Matching
Matching Applications
Domino tilings, rook placements, DAG path covers, poset width, and "maximum non-attacking set" — five reductions, one algorithm.
The five shapes to memorise
- Domino tiling of a board with holes: colour the board like a chessboard; each domino covers one black and one white cell ⇒ build the bipartite graph (black cell → adjacent white cell). A tiling covering the maximum number of cells = a maximum matching; a tiling of the whole board exists iff the matching is perfect and the colour classes are equal (the colour-count check is the classic quick rejection).
- Non-attacking rooks / queens on marked cells: maximum number of rooks with no two in a row-and-column conflict = matching on (row, column) pairs. For "minimum number of rooks covering all marked cells" = minimum vertex cover = the same matching, by Kőnig (Kőnig's Theorem and Minimum Covers).
- Minimum path cover of a DAG (vertex-disjoint directed paths covering every vertex): split v → vout, vin; answer = n - |M|. If paths may share vertices, it becomes a flow with vertex capacities (Max Flow: Ford–Fulkerson, Dinic, Push–Relabel).
- Poset width / Dilworth: maximum antichain = minimum chain cover; build x → y for x < y and use the transitive closure — so the reduction is "matching on the closure", O(n3) with Floyd–Warshall (Floyd–Warshall) then HK.
- Maximum independent set in a bipartite graph = n − min cover: "largest set of objects with no conflict pair" — scheduling with mutual exclusions, "keep the most shows". Do not confuse this with "delete the fewest vertices to make the graph bipartite", which is NP-hard (odd-cycle transversal); independence in a graph that is already bipartite is the free case.
Given a DAG with n vertices, cover all vertices with the fewest directed paths (each vertex in exactly one path). Each matching edge uout → vin means "the path continues from u to v", i.e. it saves one path: start with n single-vertex paths, and each such link merges two into one. So the count is n - |M|, and the paths themselves are read off the successors. Adding "at most K paths" or "each path has length ≤ L" is no longer matching — those need flow with an extra layer or become NP-hard; know that the clean version is exactly the unconstrained one.
If a complete domino tiling of a board with holes does not exist, the certificate is either unequal colour-class sizes, or a vertex cover of the cell-adjacency graph smaller than the number of cells/2 — i.e. the matching itself is the proof. For the classic "remove two opposite corners of a chessboard" argument, the cover is one colour class: the obstruction is exactly what Kőnig names.
- Tromino/L-tile tilings: not bipartite-2-to-1; usually DP over rows/columns (Linear Recurrences from Graphs and Matrices) or a checker invariant,
- domino tilings counted (not "does one exist"): that is the permanent/Pfaffian world — for a planar bipartite graph, Kasteleyn: # perfect matchings = √(|det K|) with a signed adjacency. CSES "Counting Tilings" (2181) is a transfer-matrix DP, not a determinant — do not confuse existence (matching), counting (Pfaffian/DP), and optimisation (min-cost matching),
- tilings of a region by rectangles of size ≥ 2 with minimum cost: that is a flow with submodular costs, and generally NP-hard once the pieces are not "1×2 or 2×1".
Other places matching is the hidden half
- Stable marriage / hospital-residents: Gale–Shapley produces a matching with an optimality property, not a maximum; the "minimum regret" variants become bipartite matching + binary search on a threshold,
- Assignment of tasks to machines with a capacity k: replace each machine by k clones (matching) or use flow with capacity k (same thing, less memory),
- Graph bipartiteness is a precondition, not a step: check it with 2-colouring first (Bipartite Graphs and 2-Colouring); if the graph is not bipartite, most of these reductions are dead, and the same question (e.g. maximum independent set) becomes NP-hard (The NP-complete Graph Problems Worth Knowing),
- Board games / "who wins on this bipartite graph": a perfect matching gives the second player a pairing strategy — a standard olympiad proof technique (The Extremal Principle's matching-based strategy examples).
Before trusting a matching reduction, answer three questions: (1) does each matching edge correspond to exactly one decision, and does every decision set form a matching (the "no two share a vertex" direction — usually the one people forget); (2) is maximizing |M| the same as optimizing the problem's objective, or only "as many as possible"?; (3) if the problem wants a minimum (of something over all objects), do you have a duality (Kőnig, min-cut, Dilworth) that makes the matching give the minimum — otherwise you are computing the wrong extremum.