Maximum Matchings and Popularity

.Let \(G = (A ∪ B, E)\) be a bipartite graph where every node has a strict ranking of its neighbors. For any node, its preferences over neighbors extend naturally to preferences over matchings. A maximum matching \(M\) in \(G\) is a popular max-matching if there is no maximum matching more popular than \(M\). In other words, for any maximum matching \(N\), the number of nodes that prefer \(M\) to \(N\) is at least the number of nodes that prefer \(N\) to \(M\). It is known that popular max-matchings always exist in \(G\) and one such matching can be efficiently computed. In this paper we are in the weighted setting, i.e., there is a cost function \(c: E → R\), and our goal is to find a min-cost popular max-matching. We prove that such a matching can be computed in polynomial time by showing a compact extended formulation for the popular max-matching polytope. By contrast, it is known that the popular matching polytope has near-exponential extension complexity and finding a min-cost popular matching is NP-hard. We also consider Pareto-optimality. Though it is easy to find a Pareto-optimal matching/max-matching, we show that it is NP-hard to find a min-cost Pareto-optimal matching/max-matching.Keywordsbipartite graphsstable matchingsdual certificatesMSC codes68W9968Q17