Bipartite Matching (Augmenting Paths)

This is an extension topic beyond most interviews; it pays off when a hard problem is secretly a one-to-one assignment, or asks for the fewest rows, columns or cells that "cover" all conflicts, which bipartite matching answers exactly.

Intuition

A matching is a set of edges with no shared endpoint: each vertex is paired with at most one partner. In a bipartite graph (left side L, right side R) that is exactly "assign workers to jobs, each worker at most one job, each job at most one worker".

The key object is an augmenting path: a path that starts at an unmatched left vertex, alternates between non-matching and matching edges, and ends at an unmatched right vertex. Flipping every edge on it (matched becomes unmatched and vice versa) adds one pair. Berge's lemma: a matching is maximum exactly when no augmenting path exists. So the algorithm is: keep finding augmenting paths.

Kuhn's algorithm finds them with a DFS from each left vertex u: try every neighbor v; if v is free, take it; if v is taken by u2, recursively ask u2 to move to another right vertex. A per-attempt seen set prevents loops.

Several classic quantities follow from the maximum matching size M in a bipartite graph:

• Minimum vertex cover (fewest vertices touching every edge) = M (König's theorem), and the proof builds the cover.
• Maximum independent set (most vertices with no edge between them) = |L| + |R| - M, because the complement of a vertex cover is independent.
• Minimum path cover of a DAG (fewest vertex-disjoint paths covering every vertex) = n - M on the split graph (left copy u_out, right copy v_in, an edge per DAG edge): every matched edge glues two path pieces together.
• Hall's theorem: all of L can be matched iff every subset S of L has at least |S| distinct neighbors.

In general (non-bipartite) graphs these shortcuts break, and maximum matching needs the much harder blossom algorithm.

When to use it in interviews / OAs

• One-to-one assignment maximizing the number of pairs: applicants to jobs, students to seats, people to tasks they are qualified for.
• Grid problems with a chessboard structure (neighbors always differ in (r + c) % 2): maximum dominoes, "minimum cells to flip so that no two adjacent ones remain" (a minimum vertex cover), seating with no adjacent conflicts (a maximum independent set).
• "Fewest rows or columns to cover all marked cells": rows on the left, columns on the right, each mark an edge; the answer is a minimum vertex cover.
• "Fewest chains or workers to execute tasks with precedence": minimum path cover of a DAG.
• When n is tiny (up to about 12 to 15), bitmask DP over assignments is the alternative.

Template

Kuhn's algorithm

import sys


def max_bipartite_matching(n_left: int, n_right: int, adj: list[list[int]]) -> tuple[int, list[int]]:
    # adj[u] = right vertices adjacent to left vertex u
    # returns (size, match_right) with match_right[v] = left partner of v, or -1
    sys.setrecursionlimit(max(1000, 2 * n_left + 10))
    match_right = [-1] * n_right

    def try_augment(u: int, seen: list[bool]) -> bool:
        for v in adj[u]:
            if not seen[v]:
                seen[v] = True
                # v is free, or its current partner can move somewhere else
                if match_right[v] == -1 or try_augment(match_right[v], seen):
                    match_right[v] = u
                    return True
        return False

    size = 0
    for u in range(n_left):
        if try_augment(u, [False] * n_right):
            size += 1
    return size, match_right

Minimum vertex cover (König's construction)

From every unmatched left vertex, walk alternating paths (left to right on non-matching edges, right to left on matching edges). Let Z be everything reached. The cover is the unreached left vertices plus the reached right vertices.

def min_vertex_cover(n_left: int, n_right: int, adj: list[list[int]]) -> tuple[list[int], list[int]]:
    _, match_right = max_bipartite_matching(n_left, n_right, adj)
    match_left = [-1] * n_left
    for v, u in enumerate(match_right):
        if u != -1:
            match_left[u] = v
    seen_l, seen_r = [False] * n_left, [False] * n_right
    stack = [u for u in range(n_left) if match_left[u] == -1]
    for u in stack:
        seen_l[u] = True
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v != match_left[u] and not seen_r[v]:
                seen_r[v] = True
                w = match_right[v]  # every reached right vertex is matched
                if w != -1 and not seen_l[w]:
                    seen_l[w] = True
                    stack.append(w)
    left = [u for u in range(n_left) if not seen_l[u]]
    right = [v for v in range(n_right) if seen_r[v]]
    return left, right  # len(left) + len(right) == maximum matching size

Minimum path cover of a DAG

def min_path_cover_dag(n: int, edges: list[tuple[int, int]]) -> int:
    adj: list[list[int]] = [[] for _ in range(n)]
    for u, v in edges:  # u_out (left) -> v_in (right)
        adj[u].append(v)
    matched, _ = max_bipartite_matching(n, n, adj)
    return n - matched  # each matched edge merges two paths into one

Complexity

Kuhn's algorithm is O(|L| * E): one DFS of O(E) per left vertex. That handles a few thousand vertices comfortably. Put the smaller side on the left. For large inputs, Hopcroft-Karp (O(E * sqrt(V))) or a max-flow algorithm on the unit network is the upgrade. The vertex cover construction and path cover add O(V + E).

Common pitfalls

• Resetting seen incorrectly. It must be fresh for every left vertex's attempt; reusing it across attempts misses augmenting paths, and sharing it within one attempt is what keeps the DFS linear.
• Using it on non-bipartite graphs. Kuhn's algorithm can return a non-maximum matching on graphs with odd cycles. Two-color first if the sides are not given.
• Mixing up indices of the two sides; keep separate ranges (or offset the right side) and separate match arrays.
• Path cover in a graph with cycles. The n - M formula is only valid for DAGs; with cycles, matched edges can form loops.
• Paths that may share vertices. If paths may overlap, first take the transitive closure of the DAG, then apply the same formula.
• Recursion depth. An augmenting path can be as long as the number of left vertices; raise the limit (as above) or write the DFS iteratively for big inputs.

Interview variations

• Maximum number of accepted invitations / job assignment. Plain maximum matching.
• Minimum operations to remove adjacent ones in a grid. Cells with value 1 form a bipartite graph by (r + c) parity; the answer is a minimum vertex cover, i.e. the matching size.
• Maximum students taking an exam (seats with no cheating neighbors). Maximum independent set on a bipartite conflict graph: available seats minus the matching (bitmask DP over rows also works).
• Fewest lines to cover all marked cells. Rows and columns as the two sides.
• Minimum number of chains (Dilworth). For a partial order, the minimum number of chains covering everything equals the maximum antichain, and it is computed as a path cover on the transitive closure.
• Weighted assignment (maximize total score) needs the Hungarian algorithm or min-cost flow; beyond interview scope, and small n is usually a bitmask DP.