Algorithm Deep Dive: Hopcroft-Karp Algorithm

A Bit of History

John Hopcroft and Richard Karp (Edmonds-Karp's Karp, once again) published this algorithm in 1973 in a paper titled, with refreshing directness, "An $n^{5/2}$ Algorithm for Maximum Matchings in Bipartite Graphs." Hopcroft would go on to share the 1986 Turing Award with Robert Tarjan (already a recurring figure in this series, from Parts 6, 8, and the SCC deep dives) — recognized jointly for foundational contributions to algorithm and data structure design, with this matching algorithm standing as one of the concrete highlights of that body of work.

Working Principle

Recall Berge's theorem from Part 16: a matching is maximum exactly when no augmenting path exists. A naive algorithm finds one augmenting path at a time (via BFS or DFS) and augments, requiring up to $O(V)$ augmentations, each costing $O(E)$ to find — giving $O(VE)$ overall, no better than generic max-flow. Hopcroft-Karp's insight: in a single phase, find the shortest augmenting-path length $k$ via one BFS from all unmatched left-side vertices simultaneously, then use DFS to greedily extract a maximal set of vertex-disjoint augmenting paths, all of length exactly $k$, and augment along all of them at once. Repeat phases until no augmenting path remains.

Analogy: Filling Many Seats in One Coordinated Pass

Instead of seating one person into one dinner-party arrangement at a time and re-shuffling the whole table each time (a new BFS/DFS per augmentation), Hopcroft-Karp finds the shortest possible "chain of swaps" needed, then simultaneously seats as many people as possible using disjoint chains of exactly that length — before moving on to consider longer chains in the next round. Doing many independent improvements per pass, rather than one improvement per pass, is exactly what shrinks the total number of passes needed.

Why O(√V) Phases Suffice

The key counting argument: after $k$ phases, the shortest remaining augmenting path has length at least $k+1$ (each phase exhausts all augmenting paths of the current shortest length, forcing the next phase's shortest path strictly longer — a direct extension of the "distances are non-decreasing" idea from Edmonds-Karp). Since a matching can differ from a maximum matching by at most $\sqrt{V}$ vertex-disjoint augmenting paths whenever the shortest augmenting path already exceeds $\sqrt{V}$ in length (a counting argument bounding how many disjoint paths of a given minimum length can fit in a graph of size $V$), at most $O(\sqrt{V})$ phases are ever needed before the matching is provably maximum.

Complexity Analysis

$O(\sqrt{V})$ phases, each costing $O(E)$ for the BFS layering plus $O(E)$ for the DFS-based disjoint-path extraction:

$$\text{Time: } O(E\sqrt{V}) \qquad \text{Space: } O(V + E)$$

This is a substantial improvement over generic Edmonds-Karp's $O(VE)$ applied to the same unit-capacity bipartite-matching flow network from Part 16 — exploiting the very specific structure (unit capacities, bipartite layout) that a fully general max-flow algorithm can't assume.

Implementation

from collections import deque

def hopcroft_karp(left_vertices, adj):
    """
    left_vertices: list of left-side vertices.
    adj: dict[left_vertex] -> list[right_vertex]  (bipartite adjacency).
    Returns dict matching each matched left vertex to its right partner.
    """
    NIL = None
    pair_left = {u: NIL for u in left_vertices}
    pair_right = {}
    dist = {}

    def bfs():
        queue = deque()
        for u in left_vertices:
            if pair_left[u] is NIL:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = float('inf')
        dist[NIL] = float('inf')

        while queue:
            u = queue.popleft()
            if dist[u] < dist[NIL]:
                for v in adj[u]:
                    pu = pair_right.get(v, NIL)
                    if dist.get(pu, float('inf')) == float('inf'):
                        dist[pu] = dist[u] + 1
                        if pu is not NIL:
                            queue.append(pu)
        return dist[NIL] != float('inf')

    def dfs(u):
        if u is NIL:
            return True
        for v in adj[u]:
            pu = pair_right.get(v, NIL)
            if dist.get(pu, float('inf')) == dist[u] + 1 and dfs(pu):
                pair_right[v] = u
                pair_left[u] = v
                return True
        dist[u] = float('inf')
        return False

    matching_size = 0
    while bfs():
        for u in left_vertices:
            if pair_left[u] is NIL:
                if dfs(u):
                    matching_size += 1

    return {u: v for u, v in pair_left.items() if v is not None}, matching_size

adj = {"A": ["1", "2"], "B": ["1"], "C": ["2", "3"]}
matching, size = hopcroft_karp(["A", "B", "C"], adj)
print(matching, size)   # e.g. {'A': '2', 'B': '1', 'C': '3'}  size=3

#include <vector>
#include <queue>
#include <unordered_map>
#include <climits>
using namespace std;

class HopcroftKarp {
    unordered_map<string, vector<string>>& adj;
    unordered_map<string, string> pairLeft, pairRight;
    unordered_map<string, int> dist;
    vector<string> leftVertices;

public:
    HopcroftKarp(vector<string>& left, unordered_map<string, vector<string>>& a)
        : adj(a), leftVertices(left) {}

    bool bfs() {
        queue<string> q;
        for (auto& u : leftVertices) {
            if (!pairLeft.count(u)) { dist[u] = 0; q.push(u); }
            else dist[u] = INT_MAX;
        }
        bool foundAugmenting = false;
        while (!q.empty()) {
            string u = q.front(); q.pop();
            for (auto& v : adj[u]) {
                if (!pairRight.count(v)) { foundAugmenting = true; }
                else {
                    string pu = pairRight[v];
                    if (dist[pu] == INT_MAX) { dist[pu] = dist[u] + 1; q.push(pu); }
                }
            }
        }
        return foundAugmenting;
    }

    bool dfs(const string& u) {
        for (auto& v : adj[u]) {
            if (!pairRight.count(v) || (dist[pairRight[v]] == dist[u] + 1 && dfs(pairRight[v]))) {
                pairRight[v] = u;
                pairLeft[u] = v;
                return true;
            }
        }
        dist[u] = INT_MAX;
        return false;
    }

    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (auto& u : leftVertices) {
                if (!pairLeft.count(u) && dfs(u)) matching++;
            }
        }
        return matching;
    }
};

import java.util.*;

class HopcroftKarp {
    Map<String, List<String>> adj;
    Map<String, String> pairLeft = new HashMap<>(), pairRight = new HashMap<>();
    Map<String, Integer> dist = new HashMap<>();
    List<String> leftVertices;

    HopcroftKarp(List<String> left, Map<String, List<String>> adjacency) {
        leftVertices = left; adj = adjacency;
    }

    boolean bfs() {
        Queue<String> queue = new LinkedList<>();
        for (String u : leftVertices) {
            if (!pairLeft.containsKey(u)) { dist.put(u, 0); queue.add(u); }
            else dist.put(u, Integer.MAX_VALUE);
        }
        boolean foundAugmenting = false;
        while (!queue.isEmpty()) {
            String u = queue.poll();
            for (String v : adj.get(u)) {
                if (!pairRight.containsKey(v)) { foundAugmenting = true; }
                else {
                    String pu = pairRight.get(v);
                    if (dist.getOrDefault(pu, Integer.MAX_VALUE) == Integer.MAX_VALUE) {
                        dist.put(pu, dist.get(u) + 1);
                        queue.add(pu);
                    }
                }
            }
        }
        return foundAugmenting;
    }

    boolean dfs(String u) {
        for (String v : adj.get(u)) {
            String pu = pairRight.get(v);
            if (pu == null || (dist.get(pu).equals(dist.get(u) + 1) && dfs(pu))) {
                pairRight.put(v, u);
                pairLeft.put(u, v);
                return true;
            }
        }
        dist.put(u, Integer.MAX_VALUE);
        return false;
    }

    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (String u : leftVertices) {
                if (!pairLeft.containsKey(u) && dfs(u)) matching++;
            }
        }
        return matching;
    }
}

Real-World Applications

Case Study

Large-Scale Task-to-Worker Assignment

Systems that must assign a large number of tasks to eligible workers (or jobs to machines, or ads to ad slots) at scale — where each side numbers in the hundreds of thousands — benefit directly from Hopcroft-Karp's asymptotic edge over generic max-flow, since the $\sqrt{V}$ factor becomes a real, measurable performance difference at that size. It remains the standard textbook algorithm for unweighted bipartite matching precisely because of this favorable scaling.

Task AssignmentLarge-Scale Matching

Exercises

Trace Hopcroft-Karp by hand on a small bipartite graph, identifying the shortest augmenting path length at each phase and confirming it strictly increases phase over phase.
Explain why finding a maximal (not necessarily maximum) set of vertex-disjoint shortest augmenting paths per phase is enough for the overall algorithm to remain correct.
Compare Hopcroft-Karp's matching result on a bipartite graph against the matching-via-max-flow reduction from Part 16 (using Edmonds-Karp), confirming both find matchings of the same maximum size.
Challenge: Implement Hopcroft-Karp and measure the actual number of phases used on bipartite graphs of increasing size, verifying the count grows roughly like $\sqrt{V}$ rather than $V$.

Limitations

Bipartite and Unweighted Only

Hopcroft-Karp's speed comes specifically from exploiting bipartite structure and unit capacities — it does not extend to general (non-bipartite) graph matching, which requires the substantially more intricate Blossom algorithm (an upcoming deep dive), nor to weighted bipartite matching (the assignment problem), which the Hungarian Algorithm handles instead.

Cookie Consent

Hopcroft-Karp Algorithm

Contents

A Bit of History

Working Principle

Analogy: Filling Many Seats in One Coordinated Pass

Why O(√V) Phases Suffice

Complexity Analysis

Implementation

Real-World Applications

Large-Scale Task-to-Worker Assignment

Exercises

Limitations

Bipartite and Unweighted Only

Cookie Consent

Hopcroft-Karp Algorithm

Contents

A Bit of History

Working Principle

Analogy: Filling Many Seats in One Coordinated Pass

Why O(√V) Phases Suffice

Complexity Analysis

Implementation

Real-World Applications

Large-Scale Task-to-Worker Assignment

Exercises

Limitations

Bipartite and Unweighted Only

Related Deep Dives

Graph Theory Series

Edmonds-Karp Algorithm

Hungarian Algorithm