Bipartite Matching, in depth: problem variants, modelling, the flow reduction, Hopcroft-Karp, Konig and Hall certificates, and weighted assignment

The problem family

Several different problems hide behind the phrase "bipartite matching". Naming yours correctly saves you from implementing the wrong algorithm.

Two of these are traps. Stable matching optimises a stability property defined by preferences, not size, so a maximum matching algorithm answers the wrong question. Online matching cannot be solved optimally, because decisions are irrevocable before the future is known.

Modelling real problems as bipartite graphs

Most of the skill in using matching is building the graph. Four habits help.

• Put the two kinds of thing on the two sides. People and shifts, tasks and machines. If an edge would ever join two items of the same kind, for example matching students into roommate pairs, the graph is not bipartite and you need general matching (Edmonds' blossom algorithm). You can test a graph with a BFS two-colouring before you rely on a bipartite algorithm.
• Encode every hard constraint by deleting edges. A nurse without ICU certification has no edge to ICU shifts. Do not encode hard rules as large weights in a cardinality problem; they belong in the graph's structure.
• Split vertices for capacity. A reviewer who can take three papers becomes three copies, each with the same edges. This is correct and simple, though a flow formulation with capacity 3 is smaller when capacities are large.
• Use time-expanded copies for scheduling. A machine available in four slots becomes four right vertices, one per slot, so the matching chooses both machine and time.

Matching as maximum flow

Matching is a special case of maximum flow, and seeing the reduction explains why everything else works. Add a source s with a capacity-1 edge to every left vertex, direct every original edge left to right with capacity 1, and add a capacity-1 edge from every right vertex to a sink t. Integral flows in this network correspond one-to-one with matchings: a unit of flow through left vertex u and right vertex v means u is matched to v, and the unit capacities stop any vertex being used twice. The integrality theorem guarantees that a maximum flow algorithm on integer capacities returns an integral flow, so the maximum flow value equals the maximum matching size.

This view pays off twice. Capacity b on the s-to-u edge gives b-matching, and costs per edge lead to min-cost flow. And the augmenting paths of Ford-Fulkerson become exactly the alternating paths of matching algorithms, which is why the residual-graph reasoning in the max flow deep dive transfers directly. In practice, though, you should not run a general flow library on a pure matching problem. Specialised algorithms exploit the unit capacities and are faster and smaller.

Hopcroft-Karp: many shortest paths per phase

Kuhn's algorithm finds one augmenting path at a time, giving O(VE) in the worst case. Hopcroft and Karp's insight was to find many shortest augmenting paths at once. Each phase does two things. A breadth-first search from all free left vertices builds layers by alternating distance and stops at the first layer containing a free right vertex. Then a depth-first search from each free left vertex finds vertex-disjoint augmenting paths that only step from one layer to the next, flipping each path as it is found.

Two facts give the bound. Each phase strictly increases the length of the shortest augmenting path. And once the shortest path is longer than √V, at most √V augmenting paths can remain, because the symmetric difference with a maximum matching consists of disjoint paths that would each need that many vertices. So there are O(√V) phases, each costing O(E), for O(E√V) total. On graphs with millions of edges that is the difference between seconds and hours.

The implementation below uses an iterative depth-first search so deep paths cannot overflow Python's recursion limit, and it marks dead-end vertices so no phase revisits them.

from collections import deque
INF = float("inf")

def hopcroft_karp(n_left, n_right, adj):
    """adj[u] lists right vertices adjacent to left vertex u."""
    match_l, match_r = [-1] * n_left, [-1] * n_right
    dist = [0] * n_left

    def bfs():
        q = deque()
        for u in range(n_left):
            dist[u] = 0 if match_l[u] == -1 else INF
            if match_l[u] == -1:
                q.append(u)
        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                w = match_r[v]
                if w == -1:
                    found = True             # a free right vertex ends a shortest path
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    q.append(w)
        return found

    def dfs(u):
        stack, path = [(u, iter(adj[u]))], []
        while stack:
            x, it = stack[-1]
            for v in it:
                w = match_r[v]
                if w == -1 or dist[w] == dist[x] + 1:
                    path.append((x, v))
                    if w == -1:              # flip the whole path
                        for a, b in path:
                            match_l[a], match_r[b] = b, a
                        return True
                    stack.append((w, iter(adj[w])))
                    break
            else:
                dist[x] = INF                # dead end for the rest of this phase
                stack.pop()
                if path:
                    path.pop()
        return False

    while bfs():
        for u in range(n_left):
            if match_l[u] == -1:
                dfs(u)
    return match_l, match_r

Certificates: Konig covers and Hall violators

A matching algorithm returns a matching, but how do you know it is maximum, and how do you explain to a stakeholder why one person is left unassigned? Two classical theorems give certificates that are cheap to compute from the final state.

König's theorem says that in a bipartite graph the maximum matching size equals the minimum vertex cover size, where a vertex cover is a set of vertices touching every edge. Any matching is at most any cover, because each matching edge needs its own cover vertex. So if you exhibit a matching and a cover of the same size, both are optimal. Hall's theorem says every left vertex can be matched if and only if every set S of left vertices has at least |S| neighbours. When a perfect matching fails, some set S has fewer neighbours than members, and that set is the human-readable explanation.

Both come from one search. Run an alternating BFS from every free left vertex after the algorithm finishes, moving left to right along any edge and right to left only along matching edges. Call the reached vertices Z. Then the left vertices not in Z plus the right vertices in Z form a minimum vertex cover, and the left vertices in Z form a Hall violator whose neighbourhood is exactly the right vertices in Z. The deficiency |S| - |N(S)| equals the number of unmatched left vertices.

def alternating_reach(n_left, adj, match_l, match_r):
    seen_l, seen_r = [False] * n_left, set()
    q = deque(u for u in range(n_left) if match_l[u] == -1)
    for u in q:
        seen_l[u] = True
    while q:
        u = q.popleft()
        for v in adj[u]:                     # any edge, left to right
            if v not in seen_r:
                seen_r.add(v)
                w = match_r[v]               # matching edge, right to left
                if w != -1 and not seen_l[w]:
                    seen_l[w] = True
                    q.append(w)
    return seen_l, seen_r

def konig_cover(n_left, adj, match_l, match_r):
    seen_l, seen_r = alternating_reach(n_left, adj, match_l, match_r)
    return [u for u in range(n_left) if not seen_l[u]], sorted(seen_r)

def hall_violator(n_left, adj, match_l, match_r):
    seen_l, seen_r = alternating_reach(n_left, adj, match_l, match_r)
    return [u for u in range(n_left) if seen_l[u]], sorted(seen_r)

These functions were checked against a brute-force maximum matching on 3,000 random graphs with up to six vertices per side: the matching size always agreed, every cover touched every edge and had exactly the matching size, and every violator had the stated neighbourhood and deficiency. Ship a similar test with your own code; matching bugs are silent, producing valid but non-maximum matchings.

Worked example: staffing on-call queues

Five engineers must staff five on-call queues, one queue each. Ana knows db and k8s, Ben knows only db, Chen knows db, net and auth, Dev knows only k8s, and Eli knows k8s and billing. Running the code above prints:

matching: {'Ana': 'db', 'Chen': 'net', 'Dev': 'k8s', 'Eli': 'billing'}
size: 4
Hall violator: ['Ana', 'Ben', 'Dev'] can only cover ['db', 'k8s']
cover: ['Chen', 'Eli', 'db', 'k8s']

Read the three outputs together. The matching staffs four queues and leaves Ben and the auth queue unassigned. The violator explains why no rearrangement helps: Ana, Ben and Dev between them only know two queues, so one of the three must sit out whatever you do. The cover proves four is optimal: every allowed pair touches Chen, Eli, db or k8s, so no matching can have more than four edges. The certificate also tells the manager where to act: auth is unstaffed because of the db and k8s bottleneck, so cross-training Ben or Dev on net or auth fixes it (billing would not, since Eli is then needed on k8s).

Maximum matchings are not unique: Chen could take auth instead of net. If some queues matter more, the problem is weighted.

Weighted assignment

When pairs have scores or costs, the question becomes the assignment problem: choose a matching that minimises total cost (or maximises total score). The Hungarian algorithm solves it in O(n³) using vertex potentials, which are the dual variables of the assignment linear program. In Python, do not write it yourself; scipy.optimize.linear_sum_assignment implements a Jonker-Volgenant variant, accepts rectangular matrices and supports maximisation.

import numpy as np
from scipy.optimize import linear_sum_assignment

cost = np.array([[4, 1, 3],
                 [2, 0, 5],
                 [3, 2, 2]])
rows, cols = linear_sum_assignment(cost)        # maximize=True for scores
print(list(zip(rows.tolist(), cols.tolist())), int(cost[rows, cols].sum()))
# [(0, 1), (1, 0), (2, 2)] 5

Note the solution: worker 1 has the cheapest single cell (cost 0) but does not get it, because giving that column to worker 0 is better for the total. Greedy assignment by cheapest cell totals 6. Forbidden pairs are best expressed with a large finite cost, followed by a check that no chosen pair carries it; an all-forbidden row then shows up as a visible violation instead of an exception. And if you need both maximum cardinality and minimum cost among maximum matchings, give forbidden pairs a cost larger than the sum of all real costs so the solver never trades a pair for savings. Problems with side constraints, such as budgets or fairness quotas, leave the matching world and belong in integer programming, where the assignment structure still makes LP relaxations unusually tight.

Choosing a method

Whatever library you use, wrap it with the certificate check above: it costs one BFS and catches both library misuse and modelling mistakes.

Failure modes

• Answering the wrong variant. Maximising pairs when the business cares about total quality, or maximising quality when every person must be placed. Write the objective down in one sentence before choosing an algorithm.
• A non-bipartite graph in disguise. Pairing items of one kind. Bipartite algorithms return a valid but possibly non-maximum matching on such graphs, with no error.
• Greedy instead of augmenting. First-come assignment produces a maximal matching, which is only guaranteed to be half the maximum size. In the worked example, if Chen is given db first, Ana then takes k8s and both Ben and Dev get nothing: three queues staffed instead of four.
• Recursion depth. Recursive DFS in Python crashes on long alternating paths; use the iterative form.
• Floating-point costs. Near-equal costs make assignments flip between runs; scale to integers or add a tie-breaker.
• Unexplained results. Shipping an assignment without the Hall violator for unmatched items invites manual overrides that make things worse. Show the bottleneck.

What to do next

1. Write one sentence naming your variant: cardinality, perfect, weighted, capacitated, stable or online.
2. Build the graph explicitly, encode hard constraints by removing edges, and run a two-colouring check if any edge could join same-kind items.
3. Implement or call Hopcroft-Karp for cardinality problems, and linear_sum_assignment for dense weighted ones.
4. Add the alternating-reach certificate: assert cover size equals matching size in tests, and report the Hall violator for any unmatched vertices.
5. Write a brute-force checker for graphs with up to six vertices per side and run a few thousand random cases in CI.
6. If capacities, lower bounds or costs on paths appear, move the model to max flow or min-cost flow; if budgets or quotas appear, move it to integer programming.