Bipartite matching

The problem

Two groups, and a list of which members of one may be paired with members of the other: developers and the tickets they know how to fix, nurses and the shifts they can work, students and the projects they qualify for. Pair up as many as possible, with nobody in either group used twice. That's maximum bipartite matching: "bipartite" because every allowed pair crosses between the two groups.

It shows up wherever one-to-one assignments are made: assigning jobs to machines, ads to slots, reviewers to papers, or drivers to riders in a single round of a ride-hailing app. Weighted versions, where each pair has a value or cost, solve assignment problems in logistics and staffing.

A flow problem in disguise

Add a source with a pipe to every member of the left group, a sink with a pipe from every member of the right group, and turn each allowed pair into a pipe from left to right. Give every pipe capacity 1.

Every unit of flow travels source → someone → someone → sink, which is exactly one matched pair, and the capacities stop anyone being used twice. Because capacities are whole numbers, some maximum flow is whole too, so the maximum flow equals the maximum matching. Switch the lab to "Flow network" to watch the very same steps as pipes. This trick of solving a new problem by translating it into one you already know is called a reduction, and it's one of the most useful ideas in algorithms.

Augmenting paths, in matching terms

In the flow network an augmenting path may use backward arcs, which cancel flow sent earlier. Translated back, the path alternates: it adds a new pair, undoes an existing one, adds another, and so on, starting and ending at people who are still free. Flipping every pair on it matches one more pair than before. In the lab, added pairs are amber and undone ones are dashed red.

That's exactly what greedy can't do. Greedy grabs the first allowed pair it sees and never reconsiders, so an early choice can block a better arrangement. The "Greedy trap" example is built for that: greedy matches three students, while rerouting finds a place for all four.

Why stop when no path exists? Claude Berge proved in 1957 that a matching is maximum exactly when no augmenting path exists. In the flow picture, the minimum cut also gives a certificate: Kőnig's theorem says the size of a maximum matching equals the size of the smallest set of people that touches every allowed pair.

Data structures

• Adjacency lists for the allowed pairs, so the search scans only real options.
• A match array per side: partner[left] and partner[right], −1 when free. Dedicated matching code skips the flow network and walks these arrays directly; following a path means hopping between them.
• A queue or stack for the search, and a visited flag per node so each search is linear in the size of the graph.

The algorithms

Every matching path adds one pair, so at most min(left, right) paths are ever needed: that's why the plain augmenting-path method is already polynomial here, without the worries about capacities that affect general max flow. Dinic's algorithm on this unit-capacity network is the same idea as Hopcroft–Karp.

Beyond this lab

• Weighted matching. When pairs have different values, the Hungarian method or min-cost flow finds the best total, not just the most pairs.
• Stable matching. When both sides have preferences, Gale and Shapley's deferred acceptance finds pairings nobody wants to break. Variants assign medical residents to hospitals and students to schools.
• General graphs. When anyone can pair with anyone, as in kidney exchanges or roommate assignment, odd cycles break the simple path argument, and Edmonds' blossom algorithm is needed.

A little history

Dénes Kőnig proved his matching theorem in 1931, and Philip Hall's 1935 "marriage theorem" says when everyone on one side can be matched: every group must, together, be allowed at least as many partners as it has members. Harold Kuhn named the Hungarian method in 1955 after Kőnig and Jenő Egerváry, whose work it builds on. John Hopcroft and Richard Karp published their faster algorithm in 1973, and David Gale and Lloyd Shapley's 1962 paper on stable matching later contributed to Shapley's 2012 Nobel Prize in economics, shared with Alvin Roth.