7. Matchings

In this chapter, we discuss algorithms for computing matchings efficiently.

• Section 7.1 introduces what a matching is and defines various properties of matchings we may want to optimize in the matchings we compute. These include the size of the matching or the weight of the matching (if the edges have weights). We also consider "perfect matchings", which ensure that every vertex in the graph is an endpoint of an edge in the matching. Such a matching may not always exist.

• In Section 7.2, we discuss how to compute a maximal matching as a warm-up exercise.¹ This type of matching provides only a very weak maximality guarantee: Any subset of the edges in \(G\) that is a proper superset of a maximal matching \(M\) is not a matching. In other words, we cannot add more edges to a maximal matching while keeping it a matching.

• In Section 7.3, we discuss how different matching problems on bipartite graphs can be formulated as flow problems and can thus be solved using the network flow algorithms we discussed in Chapters 5 and 6.

The remainder of this chapter discusses more efficient algorithms for computing different kinds of matchings directly, without using a reduction to network flows:

• We discuss two algorithms for finding maximum-cardinality matchings in bipartite graphs in Section 7.4.

• In Section 7.5, we discuss how to find a minimum-weight perfect matching in a complete bipartite graph.

• In Section 7.6, we show how to extend this algorithm to find both a minimum-weight perfect matching in an arbitrary bipartite graph (if such a matching exists) and a maximum-weight matching in an arbitrary bipartite graph.

• In Section 7.7, we discuss how to compute a maximum-cardinality matching in an arbitrary graph.