Chapter 25: Matchings in Bipartite Graphs: Stable Marriage and the Hungarian Algorithm

The foundation of maximum bipartite matching rests on augmenting paths — alternating paths between matched and unmatched edges that begin and end at unmatched vertices — where Lemma 25.1 establishes that taking the symmetric difference of a matching with an augmenting path increases the matching size by one, and its corollary confirms that a matching is maximum if and only if no augmenting path exists. The Hopcroft-Karp algorithm achieves maximum matching in O(√V × E) time by alternating between a BFS phase that builds a layered graph of shortest augmenting paths and a DFS phase that extracts a maximal set of vertex-disjoint augmenting paths simultaneously, iterating until no augmenting paths remain. The stable matching problem adds preference rankings to both sides, defining a stable matching as one with no blocking pair — an unmatched couple who would mutually prefer each other over their current partners — and the Gale-Shapley algorithm resolves this in O(n²) time by having one side propose in order of preference while the other side tentatively accepts its best offer, always terminating in a stable matching that is provably optimal for the proposing side and worst-case for the other. The Hungarian algorithm addresses the weighted assignment problem — finding a maximum-weight perfect matching in an equal-sized bipartite graph — by maintaining a feasible vertex labeling where the sum of labels on any edge does not exceed its weight, focusing search on the equality subgraph of tight edges where label sums exactly match edge weights, and iteratively augmenting the matching or updating labels to introduce new tight edges until a perfect matching is found, running in O(n⁴) time with optimized versions reaching O(n³).