Maximum Bipartite Matching: König's Theorem, Hall's Marriage Theorem & Hopcroft-Karp O(E√V)

Alternating Paths, Berge's Lemma & Hopcroft-Karp $O(E \sqrt{V})$

Given a matching $M$, a vertex is matched if it is incident to an edge in $M$, and free (unmatched) otherwise. An alternating path alternates between unmatched edges ($E \setminus M$) and matched edges ($M$). An augmenting path $P$ is an alternating path that both starts at a free vertex in $L$ and ends at a free vertex in $R$. Flipping the membership of edges along $P$ ($M' = M \oplus P$) replaces $k$ matched edges with $k + 1$ unmatched edges, increasing $|M|$ by $1$!

How Hopcroft-Karp Achieves $O(E \sqrt{V})$

While Kuhn's algorithm finds one augmenting path per $O(E)$ DFS ($O(V E)$ total), Hopcroft-Karp mirrors Dinic's algorithm on the bipartite graph directly:

1. Multi-Source BFS from all free $u \in L$: Assigns distances dist[u] along alternating layers until the shortest augmenting path length $k$ to a free vertex in $R$ is reached.
2. Simultaneous Vertex-Disjoint DFS: Finds a maximal set of vertex-disjoint shortest augmenting paths of length $k$ in $O(E)$ time and flips all of them. Because the shortest augmenting path length strictly increases each phase, at most $2\sqrt{V}$ phases occur!

Production C++20 Implementation: Hopcroft-Karp with König Minimum Vertex Cover

#include <vector>
#include <queue>
#include <limits>

class HopcroftKarp {
public:
    HopcroftKarp(int nLeft, int nRight)
        : nL(nLeft), nR(nRight), adj(nLeft), matchL(nLeft, -1), matchR(nRight, -1), dist(nLeft) {}

    void addEdge(int u, int v) { adj[u].push_back(v); }

    int maxMatching() {
        int matching = 0;
        while (bfs()) {
            for (int u = 0; u < nL; ++u) {
                if (matchL[u] == -1 && dfs(u)) {
                    ++matching;
                }
            }
        }
        return matching;
    }

    // Returns {chosenLeftNodes, chosenRightNodes} forming a Minimum Vertex Cover
    std::pair<std::vector<int>, std::vector<int>> minVertexCover() {
        std::vector<uint8_t> visL(nL, 0), visR(nR, 0);
        std::queue<int> q;
        for (int u = 0; u < nL; ++u) {
            if (matchL[u] == -1) {
                visL[u] = 1;
                q.push(u);
            }
        }
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (v != matchL[u] && !visR[v]) {
                    visR[v] = 1;
                    int nextU = matchR[v];
                    if (nextU != -1 && !visL[nextU]) {
                        visL[nextU] = 1;
                        q.push(nextU);
                    }
                }
            }
        }
        std::vector<int> coverL, coverR;
        for (int u = 0; u < nL; ++u) if (!visL[u]) coverL.push_back(u); // L  Z
        for (int v = 0; v < nR; ++v) if (visR[v]) coverR.push_back(v);  // R n Z
        return {coverL, coverR};
    }

private:
    static constexpr int INF = 1e9;
    int nL, nR;
    std::vector<std::vector<int>> adj;
    std::vector<int> matchL, matchR, dist;

    bool bfs() {
        std::queue<int> q;
        for (int u = 0; u < nL; ++u) {
            if (matchL[u] == -1) {
                dist[u] = 0;
                q.push(u);
            } else {
                dist[u] = INF;
            }
        }
        bool foundAugmenting = false;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                int nextU = matchR[v];
                if (nextU == -1) {
                    foundAugmenting = true;
                } else if (dist[nextU] == INF) {
                    dist[nextU] = dist[u] + 1;
                    q.push(nextU);
                }
            }
        }
        return foundAugmenting;
    }

    bool dfs(int u) {
        for (int v : adj[u]) {
            int nextU = matchR[v];
            if (nextU == -1 || (dist[nextU] == dist[u] + 1 && dfs(nextU))) {
                matchL[u] = v;
                matchR[v] = u;
                return true;
            }
        }
        dist[u] = INF; // Dead-end pruning: never revisit u in this phase
        return false;
    }
};