Bipartite Matching

  • Description: Matchings in bipartite graphs — definitions (maximum matching, perfect matching, maximum-weight matching), Hopcroft-Karp for unweighted bipartite max matching in O(E√V), the Hungarian algorithm for weighted assignment, König's theorem connecting matching and vertex cover, and Hall's marriage theorem.
  • My Notion Note ID: K2C-1-2
  • Created: 2020-06-01
  • Updated: 2026-05-22
  • License: Reuse is very welcome. Please credit Yu Zhang and link back to the original on yuzhang.io

Table of Contents

1. Definitions

  • Bipartite graph G = (U ∪ V, E) — vertices split into two disjoint sets U and V; every edge has one endpoint in each. No edges within U or within V.
  • Matching M ⊆ E — set of edges sharing no common endpoint. Each vertex appears in at most one edge of M.
  • Maximum matching — matching of largest cardinality (most edges).
  • Maximal matching ≠ maximum matching — maximal means "can't add another edge without violating disjointness"; maximum means "no larger one exists anywhere."
  • Perfect matching — every vertex matched. Requires |U| = |V| and at least one matching covers all.
  • Matched / unmatched vertex — relative to a fixed M.
  • Alternating path — path whose edges alternate between matched (in M) and unmatched (not in M).
  • Augmenting path — alternating path that starts and ends at unmatched vertices. Flipping matched/unmatched along it grows M by one (Berge's theorem: M is maximum iff no augmenting path exists).
  • Weighted matching — each edge has weight w(e); goal is to maximize (or minimize) Σ w(e) over e ∈ M.

2. Why Bipartite Is Special

  • In general graphs, maximum matching is solvable in polynomial time (Edmonds' blossom algorithm, O(V²E)) but the algorithm is much more involved.
  • Bipartite graphs admit:
    • Simpler max-flow reduction — add source s connected to every u ∈ U, sink t connected to every v ∈ V, edges U → V with capacity 1. Max flow = max matching.
    • Faster algorithms — Hopcroft-Karp at O(E√V), better than general blossom.
    • Tight LP relaxation — the matching polytope on bipartite graphs has integral vertices (Birkhoff-von Neumann).
    • Clean duality theorems — König (matching ↔ vertex cover), Hall (matching ↔ neighborhood expansion).

3. Maximum Matching — Unweighted

3.1 Augmenting-path method (Hungarian-style)

  • Start with M = ∅. Repeat: find an augmenting path; if one exists, flip it (matched ↔ unmatched along the path), increasing |M| by 1. Stop when no augmenting path exists.
  • Finding an augmenting path: BFS or DFS from each unmatched vertex in U, alternating between unmatched and matched edges.
  • Complexity: O(V·E) for the simple version (one augmenting path per BFS, up to V augmentations).

3.2 Hopcroft-Karp — O(E√V)

  • Same augmenting-path idea, but each phase finds a maximal set of vertex-disjoint shortest augmenting paths (BFS to build a layered graph, then DFS to extract many paths at once).
  • Number of phases bounded by O(√V).
  • Total: O(E√V). The standard go-to for unweighted bipartite matching at scale.
// Sketch — Hopcroft-Karp on adjacency lists.
// U has size n; V has size m. adj[u] lists neighbors in V.
// pair_u[u], pair_v[v] hold the current match (-1 if none). dist[u] is BFS distance.

constexpr int INF = std::numeric_limits<int>::max();

bool bfs() {
    std::queue<int> q;
    for (int u = 0; u < n; ++u) {
        if (pair_u[u] == -1) { dist[u] = 0; q.push(u); }
        else                  dist[u] = INF;
    }
    bool found = false;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) {
            int next = pair_v[v];
            if (next == -1)            { found = true; }
            else if (dist[next] == INF){ dist[next] = dist[u] + 1; q.push(next); }
        }
    }
    return found;
}

bool dfs(int u) {
    for (int v : adj[u]) {
        int next = pair_v[v];
        if (next == -1 || (dist[next] == dist[u] + 1 && dfs(next))) {
            pair_u[u] = v;
            pair_v[v] = u;
            return true;
        }
    }
    dist[u] = INF;
    return false;
}

int hopcroft_karp() {
    std::fill(pair_u.begin(), pair_u.end(), -1);
    std::fill(pair_v.begin(), pair_v.end(), -1);
    int matching = 0;
    while (bfs()) {
        for (int u = 0; u < n; ++u)
            if (pair_u[u] == -1 && dfs(u)) ++matching;
    }
    return matching;
}

3.3 Max-flow reduction

  • Add source s → each u ∈ U (capacity 1), each v ∈ V → sink t (capacity 1), and U → V edges with capacity 1.
  • Max-flow value equals max matching. Use any max-flow algorithm (Dinic's runs in O(E√V) on unit-capacity bipartite flow networks — same bound as Hopcroft-Karp).
  • Worth doing when you already have a max-flow implementation, or when you want to extend to capacity > 1 (b-matching).

4. Maximum-Weight Matching — Hungarian Algorithm

Also known as Kuhn-Munkres algorithm. Solves the assignment problem — find a perfect matching of minimum (or maximum) total weight on a complete bipartite graph with |U| = |V| = n.

  • Classical version: O(n³) on dense graphs (cost matrix).
  • Modern variants (Edmonds-Karp adaptation): O(V³) or O(V·E·log V) depending on implementation.

High-level idea

  • Maintain dual potentials (labels) u[i] on U-side and v[j] on V-side, satisfying u[i] + v[j] ≤ w(i,j) for all i,j (or ≥ for max-weight, with sign flipped).
  • An edge (i,j) is "tight" if u[i] + v[j] = w(i,j). Build a subgraph of tight edges and try to find a perfect matching there.
  • If incomplete, adjust the potentials by δ = min(u[i] + v[j] - w(i,j)) over forbidden edges, exposing new tight edges. Re-augment. Repeat.

Used in practice via library implementations:

  • scipy.optimize.linear_sum_assignment (Jonker-Volgenant variant, O(n³) but with good constants).
  • lapsolver for fast assignment on detection tracking.
  • boost::graph has maximum_weighted_matching.
  • For very large sparse assignment, use auction algorithms (Bertsekas) or LP solvers.

5. Hall's Marriage Theorem and König's Theorem

These are the structural backbone of bipartite matching theory.

5.1 Hall's Marriage Theorem

  • A bipartite graph G = (U ∪ V, E) has a matching that saturates U iff for every subset S ⊆ U, |N(S)| ≥ |S| — every subset's neighborhood is at least as large as the subset.
  • "Marriage" because the classic phrasing — n men, n women, edges = mutual interest, perfect matching = everyone married. The condition: no group of k men is collectively interested in fewer than k women.
  • Constructive proof corresponds to an augmenting-path argument; non-constructive proof via König's theorem.

5.2 König's Theorem

  • In any bipartite graph: size of maximum matching = size of minimum vertex cover.
  • Vertex cover = smallest set of vertices touching every edge.
  • This is a special case of LP duality (max flow = min cut for the matching flow network).
  • General graphs: max matching ≤ min vertex cover, equality only for bipartite.
  • Practical use: given a max matching, König's theorem gives a polynomial algorithm for minimum vertex cover on bipartite graphs (NP-hard on general graphs).

5.3 Quoted result (from the original Notion source)

"Perfect matching is always a maximum matching (every vertex is matched; adding any edge would conflict with existing edges), but not every graph has a perfect matching."

— this is correct and falls out of the definitions in § 1.

6. Real-World Uses

  • Job assignment / scheduling — workers ↔ tasks; Hungarian algorithm for minimum cost.
  • Object tracking in computer vision — frame-to-frame detection association (Hungarian / Jonker-Volgenant).
  • Stable matching variants — Gale-Shapley solves a different problem (stable, not maximum-weight); often confused.
  • Ad / content matching — users ↔ items at scale; usually solved approximately due to size.
  • Network routing — bipartite slices of larger graphs.
  • Kidney exchange chains — actually general matching with constraints, but bipartite subproblems appear.
  • Compiler register allocation — interference graph coloring sometimes reduces to bipartite matching.

7. References