Info & Theory
A bipartite graph has two groups of vertices — here a left and a right column — with edges only between the groups. A matching picks edges so no vertex is used twice.
Augmenting paths
An augmenting path begins and ends at unmatched vertices
and alternates unmatched → matched → unmatched …
edges. Flipping every edge along it (matched ↔ unmatched) adds
exactly one edge to the matching.
The algorithm
- For each unmatched left vertex, search for an augmenting path.
- If found, flip it; the matching grows by one.
- Repeat until no augmenting path exists.
Why it is optimal
Berge's theorem: a matching is maximum exactly when it has no augmenting path. So when the search comes up empty, the matching is provably maximum.
König & complexity
By König's theorem the maximum matching equals a minimum
vertex cover. The classic augmenting-path method runs in
O(V·E); Hopcroft–Karp improves this to
O(E·√V) by augmenting many shortest paths per
phase.
Applications
Assigning workers to jobs, students to projects, kidneys to recipients, or ads to slots are all bipartite matchings.
FAQ
What is a bipartite graph?
A graph whose vertices split into two disjoint sets (left and right), so every edge connects a left vertex to a right vertex. No edge joins two vertices on the same side.
What is a matching?
A set of edges with no shared endpoints, so each vertex has at most one partner. A maximum matching has the largest possible number of edges.
What is an augmenting path?
A path between two unmatched vertices that alternates unmatched and matched edges. Flipping its edges increases the matching size by exactly one.
How does it find a maximum matching?
It repeatedly searches for an augmenting path from each unmatched left vertex and flips it. When none remains, Berge's theorem guarantees the matching is maximum.
What is Berge's theorem?
A matching is maximum if and only if it has no augmenting path. That is why the algorithm can stop as soon as the search fails.
What is a perfect matching?
A matching that pairs up every vertex, leaving none unmatched. It needs equal-sized sides and edges that allow a complete assignment.
How is it related to the assignment problem?
Assigning workers to jobs, students to projects or organs to recipients is bipartite matching: each compatible pairing is an edge.
What are Hungarian and Hopcroft–Karp?
Both use augmenting paths. The Hungarian method also handles weighted minimum-cost assignment; Hopcroft–Karp finds many shortest paths per phase for O(E·√V) time.
Does the search order matter?
The final matching size is always the same, but the exact edges chosen and the number of steps can differ with the processing order.
Where is bipartite matching used?
In job and shift scheduling, ad placement, kidney exchange, school and residency assignment, network flow and any pairing under compatibility constraints.