💞 Bipartite Matching
Augmenting paths (Hopcroft–Karp)
Controls
Stats
Matching size
0
Max possible
6
Status
Ready
Info & Theory

Bipartite matching pairs vertices from two disjoint sets — L (applicants) and R (jobs) — along edges that only ever run between the two sets. A matching is a set of edges sharing no endpoints; the goal is to find one of maximum size.

Augmenting paths

An augmenting path starts and ends at unmatched vertices and alternates: unmatched edge, matched edge, unmatched edge, … Because it begins and ends unmatched, it always contains exactly one more unmatched edge than matched edge.

Why flipping helps

Swapping the matched/unmatched status of every edge on an augmenting path turns each of its endpoints into a matched vertex while keeping every interior vertex matched (just to a different neighbour). The net effect is +1 to the matching size. A matching is maximum exactly when no augmenting path exists — this is the Berge lemma.

Hopcroft–Karp complexity

Searching for one augmenting path with a single DFS from each unmatched vertex costs O(E), and up to V searches may be needed, giving O(V·E) overall. Hopcroft–Karp instead finds a maximal batch of shortest, vertex-disjoint augmenting paths in each phase (one BFS to find shortest-path length, then DFS to extract disjoint paths), needing only O(√V) phases — O(E√V) total.

Kőnig's theorem

In any bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover (the smallest set of vertices touching every edge). This duality, known as Kőnig's theorem, links matching directly to covering and underlies many combinatorial-optimisation results.

About Bipartite Matching

Written by MySimulator Team · Reviewed by MySimulator Editorial Review

Last updated: 11 July 2026

A bipartite graph splits its vertices into two disjoint sets — here, applicants on the left and jobs on the right — with edges only running between the two sets, never within one. A matching is a subset of edges in which no vertex appears more than once; a maximum matching is the largest such subset achievable for a given graph. The classical way to grow a matching is to repeatedly search for an augmenting path: a route that starts and ends at unmatched vertices and alternates between unmatched and matched edges. Flipping every edge along that path increases the matching size by exactly one, and a matching is provably maximum precisely when no augmenting path remains. Running this search from every unmatched vertex once takes O(V·E) time; the Hopcroft–Karp algorithm improves this to O(E√V) by finding several shortest augmenting paths per phase instead of one. Beyond graph theory, bipartite matching models job assignment, course allocation, and the stable-matching problems behind school and residency placement systems.

Frequently Asked Questions

What is an augmenting path in bipartite matching?

An augmenting path is a sequence of edges that starts and ends at unmatched vertices, alternating between edges not in the current matching and edges that are in it. Finding one and flipping the status of every edge along it — matched becomes unmatched and vice versa — always increases the total matching size by exactly one.

Why does flipping an augmenting path increase the matching size by one?

An augmenting path always has one more unmatched edge than matched edge, because it begins and ends on unmatched vertices. Swapping the status of every edge on the path therefore converts k unmatched edges into matched ones and k−1 matched edges into unmatched ones, a net gain of exactly one matched edge, while every vertex on the path remains covered by exactly one matched edge.

How fast is the Hopcroft–Karp algorithm compared to a naive approach?

The naive approach — repeatedly running a single depth-first-search augmenting path from each unmatched vertex — takes O(V·E) time in the worst case, since up to V augmenting paths may be needed and each search costs O(E). Hopcroft–Karp instead finds a maximal set of shortest, vertex-disjoint augmenting paths per phase using a single BFS+DFS pass, needing only O(√V) phases, for a total O(E√V) — a substantial speed-up on large graphs.

What real-world problems are solved with bipartite matching?

Bipartite matching underlies job and task assignment (matching workers to compatible roles), university admissions and hospital residency placement (a precursor to the Gale–Shapley stable matching algorithm), and network flow problems such as scheduling and resource allocation, where maximizing the number of matched pairs directly maximizes efficient use of limited resources.