Bipartite Matching

A matching is a set of edges with no shared endpoints. In a bipartite graph, maximum matching is polynomial and unlocks a family of related results that are NP-hard on general graphs.

Kuhn’s algorithm — $O(VE)$, the one to write

Repeatedly search for an augmenting path: a path alternating unmatched/matched edges that starts and ends at unmatched vertices. Flipping it increases the matching by one.

vector<vector<int>> adj;      // left vertex -> right vertices
vector<int> matchL, matchR;   // -1 = unmatched
vector<bool> used;
 
bool tryKuhn(int u) {
    for (int v : adj[u]) {
        if (used[v]) continue;
        used[v] = true;
        if (matchR[v] == -1 || tryKuhn(matchR[v])) {
            matchR[v] = u; matchL[u] = v;
            return true;
        }
    }
    return false;
}
 
int maxMatching(int nL, int nR) {
    matchL.assign(nL, -1); matchR.assign(nR, -1);
    int res = 0;
    for (int u = 0; u < nL; u++) {
        used.assign(nR, false);
        if (tryKuhn(u)) res++;
    }
    return res;
}

Two cheap speedups

1. Greedy initialisation. Before the main loop, match any left vertex to any free neighbour. This typically removes 70-90% of the augmenting searches.
2. Randomise the adjacency order. It defeats the adversarial orderings that make Kuhn hit its worst case.

Berge’s theorem

A matching is maximum iff there is no augmenting path.

This is what makes the augmenting-path approach correct, and it holds for general graphs too — the difficulty there is finding the augmenting path, which needs blossom contraction.

The algorithms

Algorithm	Time	Notes
Kuhn	$O(VE)$	~20 lines; enough for $V\le 10^3$-ish
Hopcroft-Karp	$O(E\sqrt{V})$	phases of vertex-disjoint shortest augmenting paths
Dinic on the flow network	$O(E\sqrt{V})$	identical bound; reuse your flow template
Hungarian	$O(V^3)$	weighted (min-cost perfect matching)
MCMF	$O(VE\log V)$	weighted, more flexible

König’s theorem and its corollaries

In a bipartite graph, maximum matching = minimum vertex cover.

Quantity	Formula
Minimum vertex cover	$=$ max matching
Maximum independent set	$V-$ max matching
Minimum edge cover	$V-$ max matching (for graphs with no isolated vertices)
Minimum path cover of a DAG	$V-$ max matching of the split graph
Maximum antichain in a poset	$V-$ max matching (Dilworth, via the transitive closure)

Recovering the vertex cover: let $U$ be the unmatched left vertices; let $Z$ be everything reachable from $U$ by alternating paths. The cover is $(L\setminus Z)\cup (R\cap Z)$.

Hall’s theorem

A perfect matching saturating $L$ exists iff $|N(S)|\ge |S|$ for every $S\subseteq L$.

Rarely checkable directly (exponentially many subsets), but invaluable for proofs — and its corollary that every $k$-regular bipartite graph has a perfect matching is used constantly in constructive problems.

Minimum path cover of a DAG

Split each vertex $v$ into $v_{out}\in L$ and $v_{in}\in R$; add an edge for each DAG edge. Then

$\text{minimum number of vertex-disjoint paths covering all vertices}=V-\text{max matching}.$

For a path cover allowing overlapping paths, take the transitive closure first. This is the standard route to Dilworth’s theorem in practice.

Common modelling

• rows/columns of a grid, cells to be covered
• people to tasks, with compatibility
• dominoes on a board (colour it like a chessboard — the graph is bipartite)
• “select cells so no two are adjacent” — maximum independent set on a grid graph
• matching intervals to points

See also: General Matching · Hopcroft-Karp · Maximum Flow