Pairing one set with another — the largest number of pairs, the most stable set of pairs, and the cheapest set of pairs. Three problems, three quite different algorithms.
A matching pairs up elements of two disjoint sets so that nobody is used twice: workers to jobs, students to schools, doctors to hospitals. Chapter 25 covers three versions. Maximum bipartite matching reduces to max flow from Chapter 24 and is sped up by Hopcroft-Karp. The stable-marriage problem asks not for the most pairs but for pairs nobody wants to defect from, and is solved by the Gale-Shapley algorithm. The assignment problem adds costs and is solved by the Hungarian algorithm.
G = (V,E), a matching is a subset M ⊆ E such that no two edges in M share a vertex. A vertex covered by an edge of M is matched; otherwise it is free. A maximum matching is one of largest cardinality. A perfect matching covers every vertex.A graph is bipartite if V splits into L and R with every edge running between the two sides. Bipartite matching is far easier than general matching, and this chapter stays bipartite.
The reduction is short and exact.
Given bipartite G = (L ∪ R, E), build a flow network G′:
- add a source s with an edge s → u for every u ∈ L
- direct every original edge from L to R
- add a sink t with an edge v → t for every v ∈ R
- give every edge capacity 1s to each u ∈ L allows at most one unit through u, so at most one of its edges can be used — precisely the matching condition. Symmetrically on the right. And by the integrality theorem from Chapter 24, an integer-capacity network has an integer maximum flow, so each edge carries 0 or 1 and the flow is a set of edges. Without integrality the reduction would allow fractional half-matches and mean nothing.Cost: the max flow value is at most min(|L|, |R|) = O(V), and each augmentation costs O(E), so Ford-Fulkerson gives O(V E).
The flow language translates into matching language directly, and the direct version is how the problem is usually implemented.
M is a path that starts at a free vertex in L, ends at a free vertex in R, and alternates between edges not in M and edges in M. Flipping every edge along it — unmatched become matched and vice versa — increases the matching size by exactly one, because the path has one more unmatched edge than matched.M is maximum if and only if there is no augmenting path with respect to M. This is the matching-language statement of the max-flow min-cut condition from Chapter 24.The obvious algorithm follows: repeatedly find an augmenting path by DFS or BFS and flip it. At most O(V) augmentations, each O(E), so O(V E).
L if and only if, for every subset S ⊆ L, the neighbourhood N(S) satisfies |N(S)| ≥ |S|. A violating set S is the certificate that no perfect matching exists — the analogue of exhibiting a small cut.The analysis mirrors Edmonds-Karp. The length of the shortest augmenting path strictly increases after each phase, and once it exceeds √V only O(√V) augmentations can remain. So there are O(√V) phases, each costing O(E):
O(√V · E)| Algorithm | Time | Idea |
|---|---|---|
| Ford-Fulkerson reduction | O(V E) | One augmenting path at a time |
| Hopcroft-Karp | O(√V · E) | A maximal disjoint set of shortest paths per phase |
A different objective entirely. Here every vertex is matchable and |L| = |R| = n; the question is not how many pairs but which pairs, given that everyone has a full preference ranking of the other side.
GALE-SHAPLEY (proposal / deferred-acceptance)
1 while some proposer p is free and has not proposed to everyone
2 r = the highest-ranked receiver on p's list p has not yet asked
3 if r is free
4 tentatively match p and r
5 elseif r prefers p to their current partner p′
6 match p and r; p′ becomes free // r trades up
7 else
8 r rejects p // p stays free, moves down the listO(n²): each proposer asks each receiver at most once, so there are at most n² proposals.
p prefers r to their partner, then p must already have proposed to r and been rejected or later dropped — which means r has someone they prefer to p. So no blocking pair can exist.The weighted version. Given an n × n cost matrix, find a perfect matching of minimum total cost — assign n workers to n jobs as cheaply as possible.
Brute force is n!. The Hungarian algorithm (Kuhn-Munkres) solves it in polynomial time.
Hungarian algorithm, outline
1. Subtract the row minimum from every row.
2. Subtract the column minimum from every column.
3. Cover all zeros with the minimum number of lines.
4. If the number of lines equals n, an optimal assignment exists
among the zeros — extract it.
5. Otherwise let m be the smallest uncovered entry. Subtract m from
every uncovered entry, add m to every doubly covered entry,
and go back to step 3.Running time is O(n³) in its standard implementation. Modern presentations phrase it as maintaining a dual feasible solution (the row and column potentials) alongside a partial matching, and it is a genuine special case of linear programming — a preview of Chapter 29.
| Problem | Objective | Algorithm | Time |
|---|---|---|---|
| Maximum bipartite matching | Most pairs | Max flow / augmenting paths | O(VE) |
| Same | Most pairs | Hopcroft-Karp | O(√V E) |
| Stable marriage | No blocking pair | Gale-Shapley | O(n²) |
| Assignment | Minimum total cost | Hungarian | O(n³) |
S ⊆ L has |N(S)| < |S|.O(√V · E).O(n²), and is proposer-optimal and receiver-pessimal — which side proposes matters.O(n³), using the fact that subtracting a constant from a row or column does not change the optimal matching.Part VI is complete. Part VII is a tour of selected topics, and it opens with two chapters that change the computational model rather than the problem: Chapter 26 on parallel algorithms, where work and span replace running time, and Chapter 27 on online algorithms, where the input arrives one piece at a time and decisions cannot be revised.