Home▸Networks & Graph Theory▸Bipartite Matching — Augmenting Paths

💞 Bipartite Matching — Augmenting Paths

Match left-side nodes to right-side nodes along edges by repeatedly finding augmenting paths. Watch matched pairs lock in and unmatched vertices try new alternating paths until maximum matching is reached.

Networks & Graph Theory3DModerate60 FPS

About Bipartite Matching

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.

⚙ Under the hood

Find a maximum matching in a bipartite graph via augmenting paths flipping matched and unmatched edges — the basis of job assignment.

bipartite matchingaugmenting pathHopcroft-KarpgraphCanvas 2D

3D · Three.js / WebGL renderer · 60 FPS target · runs fully client-side, no install