---
title: "Bipartite Matching (Kuhn's Algorithm)"
summary: Augmenting paths by DFS, ten lines long, O(VE) — with the tie-breaking trick that makes it pass in practice.
difficulty: core
tags: [matching, dfs, bipartite]
time: V E
prereq: [matching/intro, trees/dfs]
see: [matching/hopcroft-karp, flow/maxflow]
---

:::definition label="The setup"
Bipartition $L \cup 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.
:::

```cpp kuhn.cpp
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++; }
```

:::theorem title="Correctness"
After every vertex of $L$ has been offered, `mt` is a maximum matching.
:::

:::proof
Each `try_kuhn(v)` either finds an augmenting path from $v$ (the recursion stack records it: $v \to$ unmatched $to$, or $v \to to \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 \in 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/intro) 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$. ∎
:::

:::note title="Read that proof as: greedy + steal-back = augmenting paths"
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).
:::

:::warning title="The four practical fixes that turn O(VE) into a passing submission"
1. **Greedy pre-pass**: first match every $v$ to *any* free neighbour, then run `try_kuhn` only on unmatched vertices. On random graphs this cuts the running time by an order of magnitude, because the DFS recursion starts shallow.
2. **Order the left side by increasing degree** when the graph is sparse-but-irregular — deep searches then happen on low-degree vertices (cheap).
3. **Do not clear `used` with a `fill` inside the loop**; the `timer_` epoch trick above keeps it $O(1)$ per start vertex and avoids an extra $O(nm)$.
4. $n = m = 5\cdot10^4$, $|E| = 10^5$: worst case $5\times10^9$ — use @matching/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.
:::

:::props title="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 — @matching/konig),
- the **forced/optional edges**: an edge is in *some* maximum matching iff it is not a "bridge-like" failure in the directed graph $G_M$ (orient unmatched $R\to L$, matched $L\to 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").
:::

:::example title="Matching as a flow — the same algorithm in disguise"
Add $s \to L$ and $R \to t$ with capacity 1, the edges with capacity 1, run Dinic (@flow/maxflow). Every phase of Dinic on this unit network finds a *maximal set of vertex-disjoint shortest* augmenting paths, which is exactly @matching/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\sqrt V)$ bound for unit networks is Hopcroft–Karp's.
:::

:::problems
- [[CSES 1696]] School Dance | https://cses.fi/problemset/task/1696 | core | output the pairs, not just the size
- [[CSES 1130]] Tree Matching | https://cses.fi/problemset/task/1130 | easy | the same objective on a tree, where DP beats augmenting paths
:::