ix. Bipartite Matching

A matching is a set of edges without common endpoints. Everything rests on Berge’s theorem: a matching is maximum iff it has no augmenting path (alternating path between two free vertices). In bipartite graphs augmenting paths are found by plain DFS/BFS, and the min-max theorems of König, Hall and Dilworth make matching a modelling tool for covers, independent sets and posets.

Algorithm	Time	Notes
Kuhn (DFS augmenting paths)	$O(VE)$, fast in practice	rounds with a shared visited array + greedy look-ahead
Hopcroft–Karp	$O(E\sqrt{V})$	phases of disjoint shortest augmenting paths
Dinic on the unit network	$O(E\sqrt{V})$	reuse the flow template
weighted	Hungarian / min-cost flow	Assignment Problem

Kuhn

struct Kuhn {
    int n, m, it = 0; vector<vector<int>> g; vector<int> ml, mr, vis;
    Kuhn(int n, int m) : n(n), m(m), g(n), ml(n, -1), mr(m, -1), vis(n) {}
    void addEdge(int u, int v) { g[u].push_back(v); }
    bool dfs(int u) {
        vis[u] = it;
        for (int v : g[u]) if (mr[v] < 0) { ml[u] = v, mr[v] = u; return true; }   // look-ahead: free neighbour
        for (int v : g[u]) if (vis[mr[v]] != it && dfs(mr[v])) { ml[u] = v, mr[v] = u; return true; }
        return false;
    }
    int run() {
        int res = 0;
        for (bool ch = true; ch;) { ch = false; it++; for (int u = 0; u < n; u++) if (ml[u] < 0 && dfs(u)) res++, ch = true; }
        return res;
    }
};

The visited array is shared by a whole round; rounds repeat until one finds nothing. Shuffle adjacency lists against adversarial tests, and seed the matching with a cheap greedy pass first (match any left vertex to any free neighbour before the main loop) — this alone typically removes 70–90% of the augmenting searches.

Hopcroft–Karp

struct HopcroftKarp {
    int n, m, lim; vector<vector<int>> g; vector<int> ml, mr, dist, it;
    HopcroftKarp(int n, int m) : n(n), m(m), g(n), ml(n, -1), mr(m, -1), dist(n), it(n) {}
    void addEdge(int u, int v) { g[u].push_back(v); }
    bool bfs() {
        queue<int> q; lim = INT_MAX;
        for (int u = 0; u < n; u++) if (ml[u] < 0) dist[u] = 0, q.push(u); else dist[u] = INT_MAX;
        while (sz(q)) {
            int u = q.front(); q.pop();
            if (dist[u] >= lim) continue;
            for (int v : g[u]) { int w = mr[v]; if (w < 0) lim = min(lim, dist[u]); else if (dist[w] == INT_MAX) dist[w] = dist[u] + 1, q.push(w); }
        }
        return lim != INT_MAX;
    }
    bool dfs(int u) {
        for (int& i = it[u]; i < sz(g[u]); i++) {
            int v = g[u][i], w = mr[v];
            if (w < 0 ? dist[u] == lim : dist[w] == dist[u] + 1 && dfs(w)) { ml[u] = v, mr[v] = u; return true; }
        }
        return false;
    }
    int run() {
        int res = 0;
        while (bfs()) { fill(all(it), 0); for (int u = 0; u < n; u++) if (ml[u] < 0 && dfs(u)) res++; }
        return res;
    }
};

Proof: Berge's theorem and the algorithms

Berge. An augmenting path $P$ gives $M△P$, larger by one. Conversely if $M^{\ast }$ is larger than $M$, the components of $M△M^{\ast }$ have max degree 2 and alternate, so they are even cycles and paths; some path has more $M^{\ast }$ edges than $M$ edges, and such a path starts and ends with $M^{\ast }$ edges at vertices free in $M$: an augmenting path for $M$.

Kuhn. A DFS from a free left vertex $u$ explores exactly the alternating paths from $u$ (unmatched edge to the right, matched edge back). If it fails, no augmenting path starts at $u$; as long as the matching does not change, no vertex visited by a failed search can be on an augmenting path from a later start either (the search from it already failed), so sharing vis within a round is sound. A round with no success therefore certifies that no free left vertex starts an augmenting path; every augmenting path in a bipartite graph has an endpoint on the left, so by Berge the matching is maximum. Each round costs $O(E)$ and the number of successful augmentations is at most $V$.

Hopcroft–Karp. Each phase BFS-layers the alternating graph from all free left vertices, lim is the length of shortest augmenting paths, and the DFS with current arcs finds a maximal set of vertex-disjoint shortest augmenting paths in $O(E)$. After the phase, the shortest augmenting path is strictly longer (the same argument as Dinic’s phases). After $\sqrt{V}$ phases every augmenting path has length $\ge \sqrt{V}$; $M△M^{\ast }$ contains $|M^{\ast }|-|M|$ vertex-disjoint augmenting paths, each with $\ge \sqrt{V}$ vertices, so $|M^{\ast }|-|M|\le \sqrt{V}$ and at most $\sqrt{V}$ more phases follow. Total $O(E\sqrt{V})$.

Berge’s theorem holds verbatim for general (non-bipartite) graphs too — the matching theory above is specifically about finding the augmenting path by plain DFS/BFS, which relies on bipartiteness; on general graphs an odd cycle can hide the path and needs blossom contraction instead (General Matching). Online bipartite matching (right vertices, or edges, arrive over time and must be matched irrevocably) is a different problem entirely — greedy achieves only a $1/2$ ratio, and the optimal randomized ranking algorithm achieves $1-1/e$.

König, Hall and the covering formulas

König: in a bipartite graph, max matching = min vertex cover. From a maximum matching, let $Z$ be the vertices reachable from free left vertices by alternating paths; the cover is $(L\setminus Z)\cup (R\cap Z)$.

Quantity	Value
minimum vertex cover	$\nu$ (max matching)
maximum independent set	$V-\nu$ (complement of a cover)
minimum edge cover (no isolated vertices)	$V-\nu$ (Gallai): matching + one edge per free vertex
maximum matching (König–Ore deficiency)	$

pair<vector<int>, vector<int>> konigCover(int n, int m, const vector<vector<int>>& g, const vector<int>& ml, const vector<int>& mr) {
    vector<char> zl(n), zr(m); vector<int> st, L, R;              // input: a maximum matching
    for (int u = 0; u < n; u++) if (ml[u] < 0) zl[u] = 1, st.push_back(u);
    while (sz(st)) {
        int u = st.back(); st.pop_back();
        for (int v : g[u]) if (!zr[v]) { zr[v] = 1; int w = mr[v]; if (w >= 0 && !zl[w]) zl[w] = 1, st.push_back(w); }
    }
    for (int u = 0; u < n; u++) if (!zl[u]) L.push_back(u);
    for (int v = 0; v < m; v++) if (zr[v]) R.push_back(v);
    return {L, R};                                                // |L| + |R| = matching size
}

Hall: $L$ can be fully matched iff $|N(S)|\ge |S|$ for all $S\subseteq L$. Corollaries: every $k$-regular bipartite graph ($k\ge 1$) has a perfect matching, hence its edges split into $k$ perfect matchings; a “for every subset, enough neighbours” condition in a constructive problem means a matching exists.

Proof: König, Hall, Gallai, regular graphs

König. Every edge needs a cover vertex and matching edges are disjoint, so cover $\ge \nu$. For the construction: an edge $(u,v)$ with $u\in Z$ has $v\in Z$ (if unmatched, the alternating search crosses it; if matched, $u$ was reached through $v$ since free left vertices are unmatched), so every edge has $u\in L\setminus Z$ or $v\in R\cap Z$: it is a cover. Every $v\in R\cap Z$ is matched (else an augmenting path exists), and its partner is in $Z$; every $u\in L\setminus Z$ is matched (free ones are in $Z$). No matching edge has both ends counted, since a matched $v\in Z$ puts its partner in $Z$. So the cover has exactly $\nu$ vertices.

Hall. Necessity is clear. If $\nu <|L|$, take a König cover $C$, $|C|=\nu <|L|$, and $S=L\setminus C$. Edges from $S$ must be covered on the right, so $N(S)\subseteq R\cap C$ and $|N(S)|\le |C|-|L\cap C|<|L|-|L\cap C|=|S|$. The same computation gives the deficiency formula $\nu =|L|-{\max }_S(|S|-|N(S)|)$.

Gallai (edge cover). Given a maximum matching, adding one edge per free vertex gives $\nu +(V-2\nu )=V-\nu$ edges. Conversely, a minimum edge cover is a forest of stars (removing an edge from a path of length 3 keeps it a cover); a forest of $k$ stars on $V$ vertices has $V-k$ edges and choosing one edge per star is a matching, so $\nu \ge k$ and the cover has $V-k\ge V-\nu$ edges.

$k$-regular. For $S\subseteq L$, the $k|S|$ edges leaving $S$ all end in $N(S)$, which has only $k|N(S)|$ edge endpoints, so $|N(S)|\ge |S|$. Removing a perfect matching leaves a $(k-1)$-regular bipartite graph; induct.

Which vertices and edges are forced

With a maximum matching $M$, orient unmatched edges $L\to R$ and matched edges $R\to L$. Let $Z_L$ = vertices reachable from free left vertices, $Z_R$ = vertices reachable from free right vertices in the reversed orientation.

• A left vertex is matched in every maximum matching iff it is not in $Z_L$ (symmetrically on the right with $Z_R$).
• An edge $(u,v)\notin M$ is in some maximum matching iff $u\in Z_L$, or $v\in Z_R$, or $u$ and $v$ lie in the same SCC of the oriented graph (an even alternating cycle). Edges of $M$ are trivially in some.
• An edge $(u,v)$ is in every maximum matching iff $(u,v)\in M$, $u\notin Z_L$, $v\notin Z_R$ and $u,v$ are in different SCCs.

struct MatchingClassifier {                                       // after a maximum matching (ml, mr)
    vector<char> zl, zr; vector<int> comp;                       // comp over n + m vertices (right v -> n + v)
    MatchingClassifier(int n, int m, const vector<vector<int>>& g, const vector<int>& ml, const vector<int>& mr) {
        vector<vector<int>> gr(m); for (int u = 0; u < n; u++) for (int v : g[u]) gr[v].push_back(u);
        zl.assign(n, 0); zr.assign(m, 0); vector<int> st;
        for (int u = 0; u < n; u++) if (ml[u] < 0) zl[u] = 1, st.push_back(u);
        while (sz(st)) { int u = st.back(); st.pop_back(); for (int v : g[u]) { int w = mr[v]; if (w >= 0 && !zl[w]) zl[w] = 1, st.push_back(w); } }
        for (int v = 0; v < m; v++) if (mr[v] < 0) zr[v] = 1, st.push_back(v);
        while (sz(st)) { int v = st.back(); st.pop_back(); for (int u : gr[v]) { int w = ml[u]; if (w >= 0 && !zr[w]) zr[w] = 1, st.push_back(w); } }
        int N = n + m, timer = 0, nc = 0; comp.assign(N, -1); vector<int> num(N, -1), low(N), stk;
        auto dfs = [&](auto& self, int x) -> void {
            num[x] = low[x] = timer++; stk.push_back(x);
            auto visit = [&](int y) { if (num[y] < 0) self(self, y), low[x] = min(low[x], low[y]); else if (comp[y] < 0) low[x] = min(low[x], num[y]); };
            if (x < n) { for (int v : g[x]) if (ml[x] != v) visit(n + v); }  // unmatched L -> R
            else if (mr[x - n] >= 0) visit(mr[x - n]);                       // matched R -> L
            if (low[x] == num[x]) { int y; do { y = stk.back(); stk.pop_back(); comp[y] = nc; } while (y != x); nc++; }
        };
        for (int x = 0; x < N; x++) if (num[x] < 0) dfs(dfs, x);
    }
    bool leftAvoidable(int u) const { return zl[u]; }
    bool rightAvoidable(int v) const { return zr[v]; }
    bool edgeInSome(int u, int v, const vector<int>& ml) const { return ml[u] == v || zl[u] || zr[v] || comp[u] == comp[sz(zl) + v]; }
    bool edgeInEvery(int u, int v, const vector<int>& ml) const { return ml[u] == v && !zl[u] && !zr[v] && comp[u] != comp[sz(zl) + v]; }
};

Proof: avoidable vertices and allowed edges

Vertices. If $u\in Z_L$ is reached from a free left $f$ by an even alternating path $P$ (ending with the matched edge into $u$, or $P$ empty if $u=f$), then $M△P$ is a maximum matching leaving $u$ free. Conversely, let $M^{\prime }$ be maximum with $u$ free in $M^{\prime }$ but matched in $M$. The component of $M△M^{\prime }$ at $u$ is a path starting at $u$ with an $M$ edge; it has even length (odd would augment one of them), so it ends at a left vertex $f$ that is covered by $M^{\prime }$ but free in $M$. Read from $f$, it is an alternating path using non-$M$ edges $L\to R$ and $M$ edges $R\to L$, so $u\in Z_L$.

Edges. If $u\in Z_L$ via $P$ from a free $f$: if $v$ lies on $P$, then $P$ from $v$‘s partner to $u$ plus $(u,v)$ closes an even alternating cycle; otherwise $P$, $(u,v)$ and $v$‘s matched edge (v is matched, else $P+(u,v)$ augments) form an even alternating path from $f$. Flipping either gives a maximum matching containing $(u,v)$. The case $v\in Z_R$ is symmetric, and a same-SCC pair gives an alternating cycle through the edge (any cycle in this orientation alternates). Conversely, if a maximum $M^{\prime }$ contains $(u,v)\notin M$, the component of $M△M^{\prime }$ through it is an even cycle (same SCC) or an even path; the path’s end that is free in $M$ is a left vertex (then reading the path from it reaches $u$ before $v$, so $u\in Z_L$) or a right vertex (symmetrically $v\in Z_R$).

Forced edges. For $(u,v)\in M$: if $u\in Z_L$ (or $v\in Z_R$) some maximum matching leaves $u$ (or $v$) free, so it avoids the edge; if $u,v$ share an SCC, a cycle through $u$ must enter $u$ by its only incoming edge $v\to u$, and flipping that alternating cycle avoids the edge. Conversely, if a maximum $M^{\prime }$ avoids $(u,v)$, the component of $M△M^{\prime }$ through it is an even cycle (same SCC) or an even path whose $M$-free end is on the left (the path reaches $v$ then $u$ through the matched edge, so $u\in Z_L$) or on the right ($v\in Z_R$).

Posets: Dilworth and Mirsky

• Dilworth: the minimum number of chains covering a poset equals the maximum antichain. Compute: transitive closure, split graph (${\text{out}}_x-{\text{in}}_y$ for $x<y$), chains $=n-\nu$; the antichain is $\{x:{\text{out}}_x\notin C,{\text{in}}_x\notin C\}$ for a König cover $C$.
• Mirsky (dual): the minimum number of antichains covering a poset equals the longest chain (group by the length of the longest chain ending at each element). For sequences this is “minimum number of non-increasing subsequences = LIS” (patience sorting).
• Disjoint paths vs chains: vertex-disjoint path cover of a DAG uses the split graph without closure (Flow Modeling).

vector<int> maxAntichain(int n, const vector<vector<char>>& less) {   // less = transitive relation, less[x][y]: x < y
    HopcroftKarp hk(n, n);
    for (int x = 0; x < n; x++) for (int y = 0; y < n; y++) if (less[x][y]) hk.addEdge(x, y);
    hk.run();
    auto [cl, cr] = konigCover(n, n, hk.g, hk.ml, hk.mr);
    vector<char> bad(n); for (int x : cl) bad[x] = 1; for (int y : cr) bad[y] = 1;
    vector<int> res; for (int x = 0; x < n; x++) if (!bad[x]) res.push_back(x);
    return res;                                                     // size = n - matching = min chain cover
}

Proof: Dilworth and Mirsky

Dilworth. A chain cover with $k$ chains uses $n-k$ “successor” pairs $x<y$ forming a matching in the split graph (each element has at most one successor and predecessor in its chain), and conversely a matching gives chains because the relation is transitive (consecutive pairs compose). So min chains $=n-\nu$. An antichain meets each chain at most once, so antichain $\le$ chains. For the construction, $C$ has $\nu$ vertices, so at most $\nu$ elements are excluded and the result has $\ge n-\nu$ elements. It is an antichain: if $x<y$ were both kept, the edge ${\text{out}}_x-{\text{in}}_y$ would be uncovered. So it is a maximum antichain and both sides equal $n-\nu$.

Mirsky. A chain meets each antichain at most once, so the number of antichains $\ge$ longest chain $h$. Let $\ell (x)$ be the number of elements of the longest chain ending at $x$. If $x<y$ then $\ell (y)>\ell (x)$, so each level $\{x:\ell (x)=i\}$ is an antichain, and there are $h$ levels.

Greedy special cases

• Convex bipartite graphs (each left vertex is adjacent to an interval $[l_i,r_i]$ of ordered right vertices; e.g. jobs and time slots): sweep the right vertices in order and give each one to the available left vertex with the smallest $r_i$ (a heap). $O((n+m)\log n)$, optimal.
• Unit-interval / points on a line matchings are usually this greedy or a sorted DP.

int convexMatching(int m, vector<pair<int, int>> iv) {             // left i adjacent to right [l, r] in 0..m-1
    sort(all(iv)); priority_queue<int, vector<int>, greater<>> pq; int res = 0, k = 0;
    for (int j = 0; j < m; j++) {
        while (k < sz(iv) && iv[k].first == j) pq.push(iv[k++].second);
        while (sz(pq) && pq.top() < j) pq.pop();
        if (sz(pq)) pq.pop(), res++;
    }
    return res;
}

Proof: earliest deadline first is optimal

Process right vertices in order. Suppose an optimal matching agrees with the greedy on all slots before $j$, and the greedy gives slot $j$ to the available left vertex $a$ with the smallest $r_a$. If the optimum leaves $j$ empty, re-assign $a$ to $j$ (freeing $a$‘s later slot, if any): same size. If the optimum gives $j$ to $b\ne a$: if $a$ is unmatched in the optimum, swap $b$ out for $a$; otherwise $a$ is matched to a later slot $j^{\prime }\le r_a\le r_b$, so $b$ can take $j^{\prime }$ (since $l_b\le j<j^{\prime }$) and $a$ takes $j$. If no left vertex is available, the slot is empty in every extension. Each step keeps an optimal matching agreeing with the greedy one slot further.

Modelling

• Rows and columns: placing non-attacking rooks on allowed cells = matching rows to columns; covering all marked cells with fewest lines = König cover.
• Grid graphs are bipartite (chessboard colouring): domino tilings, maximum independent set of cells, knights on a board.
• Perfect matching in general bipartite graphs with $n\le 20$ on one side: count with DP over subsets; the number of perfect matchings is a permanent (#P-hard in general).
• Bottleneck / threshold: binary search a parameter and test for a perfect matching.
• Vertex capacities ($b$-matching): flow with capacities on source and sink edges.
• Preference-based pairing (“everyone ranks the other side”) is a different problem, not a maximum/min-cost matching — see Stable Matching (Gale–Shapley).