Bipartite Matching: Finding Augmenting Paths

Two sides, no edges within a side

A bipartite graph splits its vertices into two disjoint groups, left and right, with every edge running from one side to the other and never within a side. A matching is a subset of edges that share no endpoints - every vertex touches at most one matching edge. The problem this simulation shows is maximum matching: pick as many disjoint edges as possible. It is the mathematical skeleton of job assignment - workers on one side, tasks on the other, an edge wherever a worker is qualified for a task - as well as of stable roommate style pairing, kidney-exchange chains, and scheduling.

The augmenting path

Start from any matching, even the empty one. An augmenting path is a path that begins at an unmatched left vertex, ends at an unmatched right vertex, and alternates: unmatched edge, matched edge, unmatched edge, and so on. Flip every edge along that path - matched edges become unmatched, unmatched edges become matched - and the matching grows by exactly one edge, because the path has one more unmatched edge than matched edge. Berge's theorem states the converse too: a matching is maximum exactly when no augmenting path exists relative to it, which gives a clean stopping criterion.

function tryAugment(u, visited) {           // Kuhn's algorithm, one DFS per left vertex
  for (const v of adj[u]) {
    if (visited.has(v)) continue;
    visited.add(v);
    if (matchR[v] === -1 || tryAugment(matchR[v], visited)) {
      matchR[v] = u; matchL[u] = v;
      return true;                            // found and flipped an augmenting path
    }
  }
  return false;
}
for (const u of leftVertices) tryAugment(u, new Set());

Kuhn's algorithm and the Hopcroft-Karp speedup

Repeating the search above for every unmatched left vertex, one at a time, is Kuhn's algorithm (also credited to the Hungarian method's matching special case). Each search is an O(E) depth-first walk, and at most V searches are needed, giving O(V times E). Hopcroft-Karp (1973) improves this by finding a maximal set of shortest, vertex-disjoint augmenting paths in one BFS-then-DFS phase, instead of one path at a time. Because the shortest augmenting path length strictly increases every phase and is bounded, only O(square root of V) phases are needed, giving O(E times square root of V) overall - a large practical win once the graph has thousands of vertices.

Konig's theorem: matching meets vertex cover

In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover - the smallest set of vertices that touches every edge. This is Konig's theorem, and it is what turns matching into a certificate: once you find a matching of size k, exhibiting a vertex cover of the same size proves, on the spot, that no larger matching exists. The same duality underlies the max-flow min-cut theorem, since bipartite matching is exactly max flow on a unit-capacity network with a source wired to the left side and a sink wired to the right.

Frequently asked questions

Try it live

Everything above runs in your browser - open Bipartite Matching and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.