---
title: "Matching Applications"
summary: Domino tilings, rook placements, DAG path covers, poset width, and "maximum non-attacking set" — five reductions, one algorithm.
difficulty: hard
tags: [matching, reductions, tilings]
prereq: [matching/konig, matching/bipartite]
see: [euler/debruijn, flow/mincut-models]
---

:::props title="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 (@matching/konig).
- **Minimum path cover of a DAG** (vertex-disjoint directed paths covering every vertex): split $v \to v_{out}, v_{in}$; answer $= n - |M|$. If paths may share vertices, it becomes a flow with vertex capacities (@flow/maxflow).
- **Poset width / Dilworth**: maximum antichain = minimum chain cover; build $x \to y$ for $x < y$ and use the *transitive closure* — so the reduction is "matching on the closure", $O(n^3)$ with Floyd–Warshall (@shortest/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.
:::

:::example title="Minimum path cover, worked"
Given a DAG with $n$ vertices, cover all vertices with the fewest directed paths (each vertex in exactly one path). Each matching edge $u_{out} \to v_{in}$ 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.
:::

:::theorem title="Tiling with dominoes: when the answer is 'no' for a reason you can print"
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.
:::

:::note title="Tilings that are NOT matching"
- **Tromino/L-tile tilings**: not bipartite-2-to-1; usually DP over rows/columns (@matrices/recurrences) 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 $= \sqrt{|\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".
:::

:::props title="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 (@foundations/bipartite); if the graph is not bipartite, most of these reductions are dead, and the same question (e.g. maximum independent set) becomes NP-hard (@complexity/npc-graphs),
- **Board games / "who wins on this bipartite graph"**: a perfect matching gives the second player a pairing strategy — a standard olympiad proof technique (@proofs/extremal's matching-based strategy examples).
:::

:::warning title="Reduction-checking ritual"
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.
:::

:::problems
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | maximum matching with explicit output — the base of every reduction above
- [[CSES 2181]] Counting Tilings | https://cses.fi/problemset/task/2181 | hard | the *counting* version: DP, not matching — the contrast is the lesson
:::