7.6. Bipartite Maximum-Weight Matching

We have discussed how to find a maximum-cardinality matching in a bipartite graph and how to find a minimum-weight perfect matching in a complete bipartite graph with the same number of vertices on each side of the bipartition (otherwise, there is no perfect matching). It is time that we turn our attention to the problem of finding a maximum-weight matching in a bipartite graph.

As we will see shortly, this problem reduces to finding a minimum-weight perfect matching in an auxiliary bipartite graph, so we can once again use the Hungarian Algorithm. In its current form, however, this algorithm is not as efficient as we would like. If the graph is complete, then \(O\bigl(n^3\bigr) = O(nm)\), so the Hungarian Algorithm at least matches the running time of the simple \(O(nm)\)-time algorithm for finding a maximum-cardinality matching. If the graph is sparse, on the other hand—\(m = O(n)\)—then \(O(nm) = O\bigl(n^2\bigr)\) and the Hungarian Algorithm takes \(O(n)\) times longer to find a matching than it takes to find a maximum-cardinality matching.

In Section 7.6.1, we show how to reduce the running time of the Hungarian Algorithm to \(O\bigl(n^2 \lg n + nm\bigr)\). In Section 7.6.2, we show how to reduce maximum-weight matching to minimum-weight perfect matching.

Throughout this section, we assume that all edges have finite costs.