Chapter 13 · Matching
Kőnig's Theorem and Minimum Covers
One alternating DFS gives the minimum vertex cover, the maximum independent set, and — with a small twist — the minimum path cover of a DAG.
#Kőnig's theorem
In a bipartite graph the maximum matching size equals the minimum vertex cover size.
Let M be a maximum matching. Run the alternating DFS from all free left vertices along edges ∉ M and back along edges ∈ M; let ZL, ZR be the left/right vertices reached. Claim C = (L ∖ ZL) ∪ (R ∩ ZR) is a vertex cover of size |M|.
Covers every edge. An edge uv with u ∈ L ∖ C means u ∈ ZL; if also v ∉ C then v ∈ R ∖ ZR. If uv ∉ M, then v would have been reached from u (the DFS follows all non-matching edges out of a reached left vertex) — contradiction. If uv ∈ M, then u is matched, and a matched left vertex is reached only through its matching edge from the right, so v ∈ ZR — contradiction. Hence every edge is covered.
Size. Each v ∈ R ∩ ZR is matched (a free right vertex would end an augmenting path, impossible for maximum M), so |R ∩ ZR| ≤ |M|, and each u ∈ L ∖ ZL that matters is matched to a right vertex in ZR... precisely: no two vertices of C are matched to each other (if uv ∈ M, u ∈ ZL or v ∈ ZR, never both directions), so |C| ≤ |M|; combined with |C| ≥ |M| (any cover exceeds any matching, Matching: Definitions and Duality) gives equality. ∎
#Extracting the cover
// after any bipartite matching (mt[] on the right side), build the cover:
vector<int> zl(n), zr(m); // reached sets
queue<int> q;
for (int u = 0; u < n; u++) if (free_left(u)) { zl[u] = 1; q.push(u); }
while (q.size()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (mt[v] != u && !zr[v]) { // non-matching edge L -> R
zr[v] = 1;
if (mt[v] != -1 && !zl[mt[v]]) { zl[mt[v]] = 1; q.push(mt[v]); } // matching edge R -> L
}
}
vector<int> cover;
for (int u = 0; u < n; u++) if (!zl[u]) cover.push_back(u); // L \ Z_L
for (int v = 0; v < m; v++) if (zr[v]) cover.push_back(n + v); // R ∩ Z_R#Consequences
Consequences, each a one-line reduction
- maximum independent set = V ∖ minimum cover, so its size is n - |M| and it is computable, not just bounded — "choose the most cells with no two attacking" (Matching Applications),
- minimum edge cover (uncovered-vertex-free set of edges): n - |M| for graphs without isolated vertices — take the matching plus one edge per unmatched vertex,
- Dilworth's theorem: in a poset, the maximum antichain size = minimum number of chains covering the set. Build the bipartite graph with an edge x → y when x < y; a matching of size k gives a chain cover of size n - k, and Kőnig's cover gives an antichain of the same size — this is the algorithm for "longest non-decreasing subsequence"-family problems,
- minimum path cover in a DAG (vertex-disjoint directed paths covering all vertices): split each v into vout, vin, add uout → vin for each DAG edge, and the answer is n - |matching| (Matching Applications),
- maximum bipartite induced matching / "2D domino placement": several of these reduce to matching on a derived graph, where the same cover argument certifies optimality.
#The min-cut view
With unit capacities on s → L and R → t and ∞ on the middle edges, every finite cut is: drop a left vertex (pay 1) or drop a right vertex (pay 1) so that no ∞ edge survives — i.e. a vertex cover. So the min cut is the min cover, and "max matching = min cover" is a special case of max-flow min-cut. The alternating DFS above is what a max flow's final residual graph is: ZL = left vertices still reachable from s.
#Output-size traps
- If the problem asks for the cover, you must run the reachability on the final matching — using the matching mid-loop gives a set that is not a cover,
- Isolated vertices: they are never in ZR but they are in L ∖ ZL only if free... an isolated left vertex is free, hence in ZL, hence not in the cover — correct; but for a maximum independent set they must be included, and they are (complement of cover), so check your sample with an isolated vertex, which is exactly where off-by-one covers die,
- For "minimum number of rooks/queens covering all marked cells" (the classic), remember it is a cover on the bipartite row–column graph, so the answer is |M|, not n - |M| — the complement only gives the largest non-attacking placement, which is the other question people ask.