Bipartite Matching & Assignment — Algorithms Course

What you'll learn

Matching pairs up two groups optimally — workers to jobs, students to schools, applicants to slots. On bipartite graphs it's solved beautifully with augmenting paths, and it's a direct application of the network flow you just learned.

By the end you'll be able to:

Recognize a bipartite graph and a matching
Find a maximum matching with augmenting paths
See matching as a flow problem, and meet the assignment problem

Bipartite graphs

A graph is bipartite if its vertices split into two sets with edges only between the sets — never within one. A matching is a set of edges with no shared endpoints; a maximum matching pairs up as many as possible:

A maximum matching (green)

Three workers paired to three jobs — a perfect matching, since every vertex is matched.

Maximum matching

The key tool is again the augmenting path: a path that alternates unmatched and matched edges, starting and ending on free vertices. Flipping every edge along it increases the matching by one. Kuhn's algorithm tries to find an augmenting path from each left vertex — if one worker's preferred job is taken, it recursively asks that job's current worker to step aside to another option:

In code

Language

bipartite_matching.py

def max_bipartite_matching(adj, n_left, n_right):
    match_right = [-1] * n_right       # right vertex -> matched left, or -1
    def augment(u, seen):
        for v in adj[u]:               # jobs u can do
            if not seen[v]:
                seen[v] = True
                # v is free, or its current owner can move aside
                if match_right[v] == -1 or augment(match_right[v], seen):
                    match_right[v] = u
                    return True
        return False
    count = 0
    for u in range(n_left):
        if augment(u, [False] * n_right):
            count += 1                 # found one more augmenting path
    return count

Note

Each augmenting search is O(E), run once per left vertex, so Kuhn's algorithm is O(V·E). The more specialized Hopcroft-Karp finds many augmenting paths at once for O(E√V).

Matching as flow

Bipartite matching is max flow: add a source S connected to every left vertex, a sink T from every right vertex, and give every edge capacity 1. The maximum flow equals the maximum matching — each unit of flow is one matched pair. That reduction, plus the last module's solver, gives you matching for free.

Key idea

König's theorem ties it together: in a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover — a special case of max-flow min-cut. Deep results like this are why flow and matching sit at the heart of combinatorial optimization.

The assignment problem

Add costs to the edges and you get the assignment problem: pair every worker to a distinct job at minimum total cost. The Hungarian algorithm solves it in O(n³) — a weighted cousin of bipartite matching, and the go-to for optimal one-to-one assignment.

Recap & quick check

Key takeaways

A bipartite graph splits into two sets with edges only between them.
A matching has no two edges sharing a vertex; maximum matching pairs the most.
Augmenting paths (alternating matched/unmatched) grow a matching by one each.
Bipartite matching reduces to max flow with unit capacities.
König's theorem: max matching = min vertex cover in bipartite graphs; weighted → Hungarian O(n³).

Quick check

1. What is a matching in a graph?

2. How does bipartite matching reduce to max flow?

3. An augmenting path for matching alternates between:

4. König's theorem relates maximum matching to:

That completes graphs. The final phase gathers strings, math, randomness, geometry, and the limits of computation. Next up: Module 30 — String Matching.