Hopcroft-Karp
Find a maximum bipartite matching faster than repeated DFS by growing many shortest augmenting paths in one phase.
Hopcroft-Karp
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Hopcroft-Karp is the maximum matching algorithm I use when a bipartite graph is large enough that the simple Kuhn DFS starts to feel slow. The main upgrade is phase-based augmentation: instead of finding one augmenting path at a time, it finds many vertex-disjoint shortest augmenting paths in the same BFS/DFS round.
When to Use It
Use it when:
the graph is bipartite,
the goal is a maximum cardinality matching,
\(O(VE)\) augmenting-path code is too slow.
Core Idea
Alternate between two steps:
BFS from all unmatched left-side vertices to compute distances in the alternating graph,
DFS that only follows edges consistent with those shortest distances to find a maximal set of shortest augmenting paths.
Key Insight
After one phase, all shortest augmenting paths disappear. Therefore the distance from free left vertices to free right vertices strictly increases from phase to phase, which limits how many phases can occur.
Worked Problem
Problem.
There are workers on the left, jobs on the right, and an edge means the worker can do that job. Find the largest number of worker-job assignments with no repeated worker or job.
Why Hopcroft-Karp fits.
Bipartite matching is exactly the right abstraction. The phase idea matters when the graph is dense or when both sides have around \(10^5\) vertices total.
Correctness Intuition
BFS layers the alternating graph by shortest augmenting-path length. DFS then uses only those shortest layers, so every augmentation in the phase has minimum length. Because the chosen paths are vertex-disjoint, they can all be applied simultaneously without conflict.
Complexity Analysis
The complexity is \(O(E\sqrt{V})\).
Implementation
The code stores the left partition explicitly and returns both the matching size and the matched partner arrays.
Common Pitfalls
Forgetting which side the BFS starts from.
Mixing 0-indexed and 1-indexed NIL conventions.
Using Hopcroft-Karp for weighted matching; that is a different problem.
Variants / Extensions
Minimum vertex cover from the final alternating-reachability state.
Dinic on the flow network when you want one shared framework.
Kuhn algorithm for smaller graphs or easier implementation.
Practice Problems
Maximum bipartite matching.
Assignment feasibility on an unweighted bipartite graph.
Derive minimum vertex cover after computing the 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 left, int right) {
graph[left].push_back(right);
}
bool bfs() {
queue<int> q;
fill(dist.begin(), dist.end(), -1);
for (int v = 0; v < n_left; ++v) {
if (match_left[v] == -1) {
dist[v] = 0;
q.push(v);
}
}
bool found = false;
while (!q.empty()) {
int v = q.front();
q.pop();
for (int to : graph[v]) {
int mate = match_right[to];
if (mate == -1) {
found = true;
} else if (dist[mate] == -1) {
dist[mate] = dist[v] + 1;
q.push(mate);
}
}
}
return found;
}
bool dfs(int v) {
for (int to : graph[v]) {
int mate = match_right[to];
if (mate == -1 || (dist[mate] == dist[v] + 1 && dfs(mate))) {
match_left[v] = to;
match_right[to] = v;
return true;
}
}
dist[v] = -1;
return false;
}
int maximum_matching() {
int matching = 0;
while (bfs()) {
for (int v = 0; v < n_left; ++v) {
if (match_left[v] == -1 && dfs(v)) {
++matching;
}
}
}
return matching;
}
};
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.