Bipartite matching
Also known as: Bipartite matching · maximum matching · Kuhn's algorithm · Hopcroft–Karp · Hopcroft–Karp algorithm · König's theorem · Hall's theorem · Hall's marriage theorem
How to pair up vertices along edges so that there are as many pairs as possible: orders and repairers, cells under dominoes, students and topics. The answer is found with alternating paths, one at a time in Kuhn's algorithm and in whole phases in Hopcroft–Karp, and when no more pairs can be found, König's theorem shows what stands in the way.
Can the dark part of a photograph be laid with dominoes so that every dark cell is covered and no domino lies on a light one? Usually not, but how close can you get, and what stands in the way? Below is the photograph “Storm” divided into cells; the cells darker than a threshold have to be covered. The Hopcroft–Karp algorithm lays dominoes phase by phase, and at the end the cells left red are those no tiling can cover. Move the threshold, change the photograph, and tap the red cells.
“Storm” has 5854 dark cells. 2923 dominoes were laid, and 8 cells were left without a partner. Four of them are explained by a simple count: colour the cells like a chessboard, and there are 2929 black ones and 2925 white ones, while a domino always covers one black and one white. The other four are harder: tap a red cell, and the scene shows a region where cells of one colour outnumber their neighbours of the other. Every red cell has such a region, and that is a theorem, not a quirk of the algorithm.
The idea
A graph is bipartite if its vertices split into two parts and edges go only between the parts: orders and repairers, students and topics, black and white cells. A matching is a set of edges with no common ends, that is, a division of some of the vertices into pairs. We need the largest.
Sometimes the parts are visible at once, sometimes they have to be found: a graph is bipartite if and only if it has no odd cycles, and one breadth-first search checks this: neighbouring layers get different colours, and an edge within a layer gives away an odd cycle. On a grid of cells the parts are the colours of the chessboard colouring: cells sharing a side are always of different colours.
Take the current pairs and find a path that starts at a free vertex on the left, ends at a free vertex on the right, and alternates edges: not in a pair, in a pair, not in a pair… Swap the roles of the edges on it, so that those that were in pairs leave and the rest join, and there is one more pair. When there is no such path, the number of pairs is the largest possible.
Such a path is called augmenting, as in the maximum flow problem, and that is no coincidence: a matching is a flow of one unit through each vertex, and an alternating path is an augmenting path in the residual network. But working with the pairs directly is simpler and faster than building a network.
Kuhn's algorithm step by step
The simplest way is to go through the vertices on the left in turn and for each one look for an augmenting path by depth-first search. The repairer we want is busy: ask their order whether it could move to another repairer; that one is busy: ask further. Repairers already asked during this search are not touched a second time. The example is made up: six orders and six repairers.
Order 2 gets Aidar because order 1 moves to Bella. Order 5 is harder: its Gaukhar holds order 4, which moves to Dina, and first the search runs into a dead end through Vadim and Bella. For order 6 there is no path at all. The last step shows why: orders 1, 2, 3 and 6 together can only take three repairers.
Why this is enough
A matching M is maximum if and only if it has no augmenting path.
If there is a path, flipping it gives a matching with one more edge. Suppose there is no path, yet there is a larger matching M′. Take the edges that lie in exactly one of the two, their symmetric difference. Each vertex has at most two such edges, one from each matching, so the difference falls apart into paths and cycles in which edges of M and M′ alternate. Cycles have equal numbers of both. Since M′ has more edges, some path contains more edges of M′ than of M: it starts and ends with edges of M′, its ends are free in M, and it is an augmenting path for M. A contradiction.
When there are no paths, there is also a short way to prove it: show a vertex cover of the same size. Each pair is an edge, and the edges of a matching have no common ends, so any cover contains at least one vertex from each pair, and there are no more pairs than vertices in any cover.
In a bipartite graph the maximum matching equals the minimum vertex cover.
Let M be maximum. Let Z be all vertices reachable by alternating paths from free vertices on the left. Take C = (left vertices outside Z) ∪ (right vertices in Z). Every edge is covered: if its left end is in Z, the right end is in Z too, since it can be reached along this edge (and if this is a matched edge, the left end entered Z through it). The size: each right vertex in Z is matched, otherwise there would be an augmenting path, and its partner on the left is also in Z; each left vertex outside Z is matched, since all free vertices on the left are in Z. So C has exactly one vertex from each pair, and |C| = |M|.
Hall's theorem follows: all vertices on the left can be matched if and only if any k of them together have at least k neighbours on the right. If pairs could not be found, the set Z on the left is the culprit: its neighbours are the right vertices in Z, and there are fewer of them. This is what the scene draws when you tap a red cell, and the same shows in the last step of the example with orders.
Code
The program builds the graph of cells of four photographs, lays dominoes with the Hopcroft–Karp algorithm, counts for comparison how many edges Kuhn would have examined, and builds the cover from the proof of König's theorem; it always has the same size as the matching. The depth-first search uses its own stack: augmenting paths on cells can be thousands of steps long, and Python's recursion would hit its depth limit.
On “Lake Issyk” 33 cells stay unpaired with a colour difference of one: the difference is only a lower bound, and a real picture has plenty of holes and narrow necks. And the comparison with Kuhn shows that on such grids it does well: on three photographs it examined about as many edges as Hopcroft–Karp, and only on “Storm” six times more.
What it costs
In Kuhn's algorithm each search costs O(E), and there is one search per vertex on the left: O(V E). It gets bad when many vertices cannot get a partner: a failed search walks everything the alternating paths reach and changes nothing, and the next one walks the same ground again. Hopcroft–Karp works in phases. One breadth-first search from all free vertices on the left at once lays the graph out in layers by the length of the shortest alternating path. Then a depth-first search that goes only from one layer to the next finds many shortest augmenting paths with no common vertices, and all of them are flipped in one phase.
There are at most 2√V phases, so the algorithm runs in O(E √V).
Each phase is O(E): a vertex from which no path was found is marked as a dead end until the end of the phase, and each edge is examined a constant number of times. After a phase the shortest augmenting path becomes strictly longer, so after √V phases all augmenting paths are longer than √V. Compare the current matching with a maximum one: their symmetric difference contains as many vertex-disjoint augmenting paths as pairs are missing, and each is longer than √V. There are only V vertices, so fewer than √V pairs are missing, and each further phase adds at least one. In all there are at most 2√V phases.
The measurement is the situation that is worst for Kuhn: twice as many orders as workers, each order suiting three random workers. The third line is Kuhn with a well-known trick: the “already asked” marks are reset only after a successful search, since a failed one changed nothing.
Kuhn grows as a square: at two thousand orders it is 60 times slower than Hopcroft–Karp in Python, and at sixteen thousand in Go more than a thousand times. The trick helps by an order of magnitude but does not change the slope: after each successful search the marks are still reset. Hopcroft–Karp's time grows almost linearly. The link with flows is direct here too: on a network with unit capacities Dinic's algorithm does the same thing, layers and a blocking flow, and runs in the same time.
Where it is used
Assignment without weights. Orders and workers, jobs and machines, flights and gates: who can be put with whom, and how to place the most. If each pair has a cost and the cheapest complete assignment is needed, that is the Hungarian algorithm; if the participants have preferences and stability is needed, the Gale–Shapley algorithm from the course chapter.
How many workers are needed. Jobs with start and end times, a worker who finishes one job can make it to another: how many workers are enough for all of them? The answer: the number of jobs minus the maximum matching in the graph “job → job that can be done next”. If the relation “can be done next” is transitive, this is Dilworth's theorem on dividing a partially ordered set into chains.
Physics. Tilings of a lattice by dominoes are the dimer model of statistical physics. In 1961 Pieter Kasteleyn and, independently, Harold Temperley with Michael Fisher found a formula for the number of such tilings of a rectangle; a chessboard has 12,988,816 of them. And if two opposite corners are cut off the board, not a single tiling remains: the same colour difference as in the scene. The philosopher Max Black proposed this puzzle in 1946.
History
Dénes Kőnig published the theorem on covers in 1931; in the same year Jenő Egerváry proved a weighted version of it. In 1935 Philip Hall formulated the condition “any k together have at least k neighbours” in the problem of a system of distinct representatives, and the playful name “the marriage theorem” stuck to it. In 1955 Harold Kuhn built on the work of Kőnig and Egerváry an algorithm for the assignment problem and called it the Hungarian method; in competitive programming the search for augmenting paths one at a time is often called Kuhn's algorithm. Claude Berge proved the lemma on augmenting paths in 1957 for all graphs, not only bipartite ones. John Hopcroft and Richard Karp published the algorithm with phases in 1973.
Problems
In the first problem you have to see the bipartite graph in a grid of cells yourself, and not trust the colour count. In the second there are more orders than repairers, and the plain Kuhn's algorithm does not make it in time.
A domino mosaic Calls and repairersData: Photographs by the site's author