Chapter 13 · Matching
Bipartite Matching (Kuhn's Algorithm)
Augmenting paths by DFS, ten lines long, O(VE) — with the tie-breaking trick that makes it pass in practice.
Bipartition L ∪ R; only edges L–R exist. mt[x] = the partner of x, or -1. A try(v) call attempts to make v matched, possibly stealing a partner and re-housing its previous match.
vector<vector<int>> g(n); // only from the left side
vector<int> mt(m, -1), used(n), timer_; // m = |R|
bool try_kuhn(int v) {
if (used[v] == timer_) return false;
used[v] = timer_;
for (int to : g[v]) {
if (mt[to] == -1 || try_kuhn(mt[to])) { mt[to] = v; return true; }
}
return false;
}
int matching = 0;
for (int v = 0; v < n; v++) { timer_++; if (try_kuhn(v)) matching++; }After every vertex of L has been offered, mt is a maximum matching.
Each try_kuhn(v) either finds an augmenting path from v (the recursion stack records it: v → unmatched to, or v → to → the previous partner's re-housing) and flips it, increasing |M| by 1, or proves that no augmenting path from v exists in the current graph restricted to the visited set. Since each successful call strictly increases the matching and each call's recursion alternates unmatched/matched edges, every flip yields a valid matching. When all v ∈ L have been processed, suppose an augmenting path P existed; take its left endpoint u — the first u on P processed... Standard: Berge's lemma (Matching: Definitions and Duality) requires no augmenting path; the classical invariant proof shows the DFS explores all reachable alternating vertices from u, so if a shorter augmenting path from any vertex existed at the end, the last successful augmentation would have used it. Formally, the algorithm maintains "no augmenting path starts at an already-processed vertex", and processing all vertices then leaves none, since the left endpoints of any augmenting path are all in L. ∎
The insight is that a plain greedy "take a free neighbour" becomes optimal exactly when you allow the displaced vertex to search again — one level of recursion is enough to implement Berge's lemma because the recursion is the alternating path. The used marker prevents revisiting a left vertex within one search (else the DFS loops inside a cycle of the alternating graph).
- Greedy pre-pass: first match every v to any free neighbour, then run
try_kuhnonly on unmatched vertices. On random graphs this cuts the running time by an order of magnitude, because the DFS recursion starts shallow. - Order the left side by increasing degree when the graph is sparse-but-irregular — deep searches then happen on low-degree vertices (cheap).
- Do not clear
usedwith afillinside the loop; thetimer_epoch trick above keeps it O(1) per start vertex and avoids an extra O(nm). - n = m = 5·104, |E| = 105: worst case 5×109 — use Hopcroft–Karp or max flow instead; if you keep Kuhn, you are betting on the average case, which is fine only when the statement's generator is random.
What one run gives you
- the maximum matching itself (
mt), - the minimum vertex cover and maximum independent set (via the alternating reachability from unmatched left vertices — Kőnig's Theorem and Minimum Covers),
- the forced/optional edges: an edge is in some maximum matching iff it is not a "bridge-like" failure in the directed graph GM (orient unmatched R→ L, matched L→ R); an edge is in every maximum matching iff it is matched and its removal drops the size, i.e. it is a bridge of that directed structure — a 5-line addition on top of the same DFS,
- perfect matching existence on a tree/convex graph, where the DFS is O(n) after ordering,
- maximum bipartite independent set = n − min cover, which is "largest set with no conflict edge" (e.g. "choose the most items, no two from the same pair").
Add s → L and R → t with capacity 1, the edges with capacity 1, run Dinic (Max Flow: Ford–Fulkerson, Dinic, Push–Relabel). Every phase of Dinic on this unit network finds a maximal set of vertex-disjoint shortest augmenting paths, which is exactly Hopcroft–Karp. So "max flow is overkill for bipartite matching" is false in the interesting sense: the flow algorithm is the matching algorithm, and Dinic's O(E√V) bound for unit networks is Hopcroft–Karp's.