7.5. Bipartite Minimum-Weight Perfect Matching

Having discussed how to compute maximum-cardinality matchings in bipartite graphs efficiently, let us now turn our attention to weighted matchings. In this section, we discuss how to find a minimum-weight perfect matching in a complete bipartite graph \(G = (U, W, E)\). This means that every edge \((u,w)\) with \(u \in U\) and \(w \in W\) is in \(G\). We also require that \(|U| = |W|\) because otherwise no perfect matching can exist. A complete bipartite graph with \(|U| = |W|\) always has a perfect matching, so the algorithm does not need to worry about the possibility that no perfect matching may exist. In Section 7.6, we will see that the same algorithm can also be used to compute minimum-weight perfect matchings and maximum-weight matchings of arbitrary bipartite graphs, but at that point, the algorithm needs to check whether a perfect matching even exists.

• The algorithm for finding a minimum-weight perfect matching, called the Hungarian Algorithm, is a very elegant applications of the primal-dual schema, so we start the discussion by reviewing, in Section 7.5.1, the main ideas of the primal-dual schema.

• In Section 7.5.2, we use these ideas to develop a first version of the Hungarian algorithm, which runs in \(O\bigl(n^4\bigr)\) time.

• We conclude this section in Section 7.5.3 by discussing an improved implementation of the Hungarian algorithm, which runs in \(O\bigl(n^3\bigr)\) time.