Hopcroft-Karp Algorithm

Matching and Augmenting Paths

Let $G=(L\cup R,E)$ be bipartite: every edge joins a left vertex to a right vertex. A matching $M$ is a set of edges with no shared endpoint. Its size $|M|$ counts how many left–right pairs have been formed, and a maximum matching has the largest possible size.

An augmenting path starts at a free left vertex, ends at a free right vertex, and alternates unmatched–matched–unmatched edges. It contains one more unmatched edge than matched edge. Flipping every edge along the path therefore increases the matching size by exactly one.

Why Flipping an Augmenting Path Works

One Phase: BFS Layers, Then a DFS Batch

A basic augmenting-path algorithm searches, flips one path, and starts over. Hopcroft–Karp amortizes the search by handling a whole maximal set of vertex-disjoint shortest augmenting paths in one phase.

1. Multi-source BFS: begin from every free left vertex at distance zero.
2. Build the alternating layered graph: move left-to-right only through unmatched edges, then right-to-left only through the right vertex's current matched edge.
3. Stop at the shortest free-right layer: once a free right vertex is reachable, record that augmenting distance and do not build deeper layers.
4. Layer-respecting DFS: from each free left vertex, follow only edges that advance exactly one BFS layer and finish at that shortest distance.
5. Flip all found paths: the DFS paths are vertex-disjoint, so their updates do not conflict.

Worked Phase: Two Paths at Once

Suppose the current matching is $M=\{A\!-!1, B\!-!2\}$. Left vertices $C,D$ and right vertices $3,4$ are free. The graph contains the alternating routes $C-1-A-3$ and $D-2-B-4$.

Correctness and the $O(\sqrt{V})$ Phase Bound

Three facts connect the phase mechanics to the final guarantee:

1. Every DFS success is a valid augmentation. Layer rules enforce alternation, and vertex-disjoint paths can be flipped together without assigning any vertex twice.
2. The shortest augmenting-path length strictly increases after a phase. DFS finds a maximal set that blocks every shortest route in the current layered graph. Any surviving augmenting path must therefore be longer.
3. No augmenting path means maximum. This is exactly Berge's theorem.

The phase count uses a short-path/long-path split. During the first $O(\sqrt{V})$ phases, the shortest augmenting length increases at least once per phase. Once that length exceeds $\sqrt{V}$, compare the current matching $M$ with a maximum matching $M^*$. Their symmetric difference decomposes into vertex-disjoint alternating cycles and paths. Every remaining augmenting component is long, so only $O(\sqrt{V})$ such components can fit among $V$ vertices. Hence the deficit $|M^*|-|M|$ is $O(\sqrt{V})$, and at most that many additional phases are possible.

Implementation

The code below numbers left vertices $0\ldots |L|-1$ and right vertices $0\ldots |R|-1$. pairU[u] is the right partner of left vertex $u$; pairV[v] is the left partner of right vertex $v$; $-1$ means free. The explicit distNil counts unmatched left-to-right steps on a shortest augmenting route, so its ordinary edge length is $2\cdot\text{distNil}-1$.

from collections import deque

def hopcroft_karp(adj, right_size):
    """adj[u] lists the right-side neighbors of left vertex u."""
    left_size = len(adj)
    FREE = -1
    INF = left_size + 1
    pair_u = [FREE] * left_size
    pair_v = [FREE] * right_size
    dist = [INF] * left_size
    dist_nil = INF

    def bfs():
        nonlocal dist_nil
        queue = deque()
        for u in range(left_size):
            if pair_u[u] == FREE:
                dist[u] = 0
                queue.append(u)
            else:
                dist[u] = INF

        dist_nil = INF
        while queue:
            u = queue.popleft()
            if dist[u] >= dist_nil:
                continue  # never build deeper than a shortest augmenting path

            for v in adj[u]:
                mate = pair_v[v]
                if mate == FREE:
                    dist_nil = dist[u] + 1
                elif dist[mate] == INF:
                    dist[mate] = dist[u] + 1
                    queue.append(mate)

        return dist_nil != INF

    def dfs(u):
        for v in adj[u]:
            mate = pair_v[v]
            if mate == FREE:
                if dist[u] + 1 != dist_nil:
                    continue
            elif dist[mate] != dist[u] + 1 or not dfs(mate):
                continue

            pair_u[u] = v
            pair_v[v] = u
            return True

        dist[u] = INF  # prune this dead end for the rest of the phase
        return False

    matching_size = 0
    while bfs():
        for u in range(left_size):
            if pair_u[u] == FREE and dfs(u):
                matching_size += 1

    return pair_u, pair_v, matching_size

# A:{1,3}, B:{2,4}, C:{1}, D:{2}; indices are zero-based.
adj = [[0, 2], [1, 3], [0], [1]]
pair_u, pair_v, size = hopcroft_karp(adj, right_size=4)
print("left partners:", pair_u)  # [2, 3, 0, 1]
print("matching size:", size)    # 4

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

class HopcroftKarp {
    static constexpr int FREE = -1;
    const vector<vector<int>>& adj;
    int leftSize, rightSize, inf, distNil;
    vector<int> pairU, pairV, dist;

    bool bfs() {
        queue<int> ready;
        for (int u = 0; u < leftSize; ++u) {
            if (pairU[u] == FREE) {
                dist[u] = 0;
                ready.push(u);
            } else {
                dist[u] = inf;
            }
        }

        distNil = inf;
        while (!ready.empty()) {
            int u = ready.front();
            ready.pop();
            if (dist[u] >= distNil) continue;

            for (int v : adj[u]) {
                int mate = pairV[v];
                if (mate == FREE) {
                    distNil = dist[u] + 1;
                } else if (dist[mate] == inf) {
                    dist[mate] = dist[u] + 1;
                    ready.push(mate);
                }
            }
        }
        return distNil != inf;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int mate = pairV[v];
            if (mate == FREE) {
                if (dist[u] + 1 != distNil) continue;
            } else if (dist[mate] != dist[u] + 1 || !dfs(mate)) {
                continue;
            }

            pairU[u] = v;
            pairV[v] = u;
            return true;
        }

        dist[u] = inf;
        return false;
    }

public:
    HopcroftKarp(const vector<vector<int>>& graph, int rightCount)
        : adj(graph), leftSize(static_cast<int>(graph.size())),
          rightSize(rightCount), inf(leftSize + 1), distNil(inf),
          pairU(leftSize, FREE), pairV(rightSize, FREE), dist(leftSize, inf) {}

    int maximumMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < leftSize; ++u)
                if (pairU[u] == FREE && dfs(u)) ++matching;
        }
        return matching;
    }

    const vector<int>& leftPartners() const { return pairU; }
};

int main() {
    vector<vector<int>> adj = {{0, 2}, {1, 3}, {0}, {1}};
    HopcroftKarp matcher(adj, 4);
    cout << "Matching size: " << matcher.maximumMatching() << '\n';
    cout << "Left partners: ";
    for (int v : matcher.leftPartners()) cout << v << ' ';
    cout << '\n';
}

import java.util.*;

class HopcroftKarp {
    private static final int FREE = -1;
    private final List<List<Integer>> adj;
    private final int leftSize, inf;
    private int distNil;
    private final int[] pairU, pairV, dist;

    HopcroftKarp(List<List<Integer>> graph, int rightSize) {
        adj = graph;
        leftSize = graph.size();
        inf = leftSize + 1;
        distNil = inf;
        pairU = new int[leftSize];
        pairV = new int[rightSize];
        dist = new int[leftSize];
        Arrays.fill(pairU, FREE);
        Arrays.fill(pairV, FREE);
    }

    private boolean bfs() {
        Deque<Integer> ready = new ArrayDeque<>();
        for (int u = 0; u < leftSize; ++u) {
            if (pairU[u] == FREE) {
                dist[u] = 0;
                ready.add(u);
            } else {
                dist[u] = inf;
            }
        }

        distNil = inf;
        while (!ready.isEmpty()) {
            int u = ready.remove();
            if (dist[u] >= distNil) continue;

            for (int v : adj.get(u)) {
                int mate = pairV[v];
                if (mate == FREE) {
                    distNil = dist[u] + 1;
                } else if (dist[mate] == inf) {
                    dist[mate] = dist[u] + 1;
                    ready.add(mate);
                }
            }
        }
        return distNil != inf;
    }

    private boolean dfs(int u) {
        for (int v : adj.get(u)) {
            int mate = pairV[v];
            if (mate == FREE) {
                if (dist[u] + 1 != distNil) continue;
            } else if (dist[mate] != dist[u] + 1 || !dfs(mate)) {
                continue;
            }

            pairU[u] = v;
            pairV[v] = u;
            return true;
        }

        dist[u] = inf;
        return false;
    }

    int maximumMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < leftSize; ++u)
                if (pairU[u] == FREE && dfs(u)) ++matching;
        }
        return matching;
    }

    int[] leftPartners() { return pairU.clone(); }

    public static void main(String[] args) {
        List<List<Integer>> adj = Arrays.asList(
            Arrays.asList(0, 2), Arrays.asList(1, 3),
            Collections.singletonList(0), Collections.singletonList(1)
        );
        HopcroftKarp matcher = new HopcroftKarp(adj, 4);
        System.out.println("Matching size: " + matcher.maximumMatching());
        System.out.println("Left partners: " + Arrays.toString(matcher.leftPartners()));
    }
}

Complexity and Alternatives

Within one phase, BFS scans the bipartite edges to build layers. DFS scans admissible edges while failed left vertices are marked unreachable for the rest of that phase. Thus a phase costs $O(E)$, not one full search per augmented path.

Here $V=|L|+|R|$. The space includes adjacency lists, two partner arrays, the BFS distance array, and the queue. For a dense bipartite graph with $|L|=|R|=n$, $V=2n$ and $E$ may be $n^2$; the edge count still dominates the actual scanning work.

Real-World Applications

Hopcroft–Karp answers a precise question: what is the largest number of compatible left–right pairs when every acceptable pair has equal value?

Pitfalls and Implementation Checklist

Exercises

1. Trace the worked graph from an empty matching. Show that phase one finds $A-1$ and $B-2$, while phase two finds both length-three augmenting paths.
2. Remove edge $B-4$. Redraw the layered graph and determine the matching returned after the next phase.
3. Explain why two augmenting paths that share a vertex cannot safely be flipped as independent updates.
4. Instrument the implementation to print distNil, the number of successful DFS calls, and matching size after every phase.
5. Construct the minimum vertex cover from the final matching using alternating reachability.
6. Compare Hopcroft–Karp with a one-path-at-a-time DFS matcher on increasingly large sparse graphs.
7. Challenge: replace recursive DFS with explicit stack frames while preserving path reconstruction and layer pruning.

Historical Note

John Hopcroft and Richard Karp introduced the algorithm in 1973. Its enduring idea is broader than matching: when many shortest improvements are independent, construct a layered search space once and apply a maximal batch before rebuilding it. That phase-based pattern reappears throughout advanced flow and matching algorithms.