Bipartite Matching
Match the two sides of a bipartite graph efficiently, and recognize when the problem is assignment rather than general flow.
Bipartite Matching
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Bipartite matching is the cleanest example of turning a structural graph question into an algorithmic primitive. Many ``pair these objects'' problems are really asking for the largest set of disjoint edges between a left side and a right side.
When to Use It
Use bipartite matching when:
the objects naturally split into two groups,
each allowed pairing links one left item to one right item,
every item can be used only a limited number of times, often exactly once.
Examples include job assignment, student-project pairing, rook placement, or scheduling with compatibility edges.
Core Idea
A matching is a set of edges with no shared endpoints. The algorithm grows the matching by finding augmenting paths: paths that alternate between unmatched and matched edges and start and end at free vertices.
Flipping the status of the edges on such a path increases the matching size by one.
Key Insight
The alternating-path view explains both correctness and implementation. Hopcroft-Karp speeds things up by finding many shortest augmenting paths in one BFS/DFS phase instead of increasing the matching by only one edge at a time.
Operations / Main Technique
build the bipartite graph from left to right,
BFS from free left vertices to compute distance layers,
DFS through those layers to find augmenting paths,
repeat until no free right vertex is reachable.
Worked example.
If \(L_1\) is free, \(R_3\) is matched to \(L_4\), and there is a path \[ L_1 \to R_3 \to L_4 \to R_2, \] where \(R_2\) is free, flipping matched and unmatched edges along that path increases the total matching size by one.
Correctness Intuition
An augmenting path always increases the matching by one because it starts and ends at free vertices and alternates edge status in between. When no augmenting path exists, the current matching is maximum. Hopcroft-Karp is still based on that fact; it only batches shortest augmenting paths together.
Complexity Analysis
Hopcroft-Karp runs in \(O(E \sqrt{V})\), which is usually much better than repeated DFS matching on larger graphs.
Implementation
The code uses Hopcroft-Karp with:
adjacency lists from the left side,
distance labels for the BFS phase,
two match arrays, one per side.
Common Pitfalls
Forgetting that the graph must be bipartite before this model applies.
Mixing left-side and right-side indexing in the match arrays.
Reaching for general max flow when plain bipartite matching is enough.
Using Kuhn's algorithm on input sizes that really need Hopcroft-Karp.
Variants / Extensions
Minimum vertex cover in bipartite graphs via Konig's theorem.
Weighted assignment, which leads to Hungarian or min-cost flow instead.
Capacity on one side by splitting or by a small flow reduction.
Practice Problems
Maximum bipartite matching on compatibility edges.
Place the maximum number of non-attacking objects on a constrained grid.
Recover a minimum vertex cover after finding a maximum matching.
References
Code
Contest-ready reference implementation for the idea explained above.
struct HopcroftKarp {
int n_left;
int n_right;
vector<vector<int>> graph;
vector<int> dist;
vector<int> match_left;
vector<int> match_right;
HopcroftKarp(int n_left, int n_right)
: n_left(n_left),
n_right(n_right),
graph(n_left),
dist(n_left),
match_left(n_left, -1),
match_right(n_right, -1) {}
void add_edge(int u, int v) {
graph[u].push_back(v);
}
bool bfs() {
queue<int> q;
fill(dist.begin(), dist.end(), -1);
for (int u = 0; u < n_left; ++u) {
if (match_left[u] == -1) {
dist[u] = 0;
q.push(u);
}
}
bool found = false;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
int next = match_right[v];
if (next == -1) {
found = true;
} else if (dist[next] == -1) {
dist[next] = dist[u] + 1;
q.push(next);
}
}
}
return found;
}
bool dfs(int u) {
for (int v : graph[u]) {
int next = match_right[v];
if (next == -1 || (dist[next] == dist[u] + 1 && dfs(next))) {
match_left[u] = v;
match_right[v] = u;
return true;
}
}
dist[u] = -1;
return false;
}
int maximum_matching() {
int matching = 0;
while (bfs()) {
for (int u = 0; u < n_left; ++u) {
if (match_left[u] == -1 && dfs(u)) {
++matching;
}
}
}
return matching;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.