Abstract. We consider the max-size popular matching problem in a roommates instance G = (V, E) with strict preference lists. A matching M is popular if there is no matching M in G such that the vertices that prefer M to M outnumber those that prefer M to M . We show it is NP-hard to compute a max-size popular matching in G. This is in contrast to the tractability of this problem in bipartite graphs where a max-size popular matching can be computed in linear time. We define a subclass of max-size popular matchings called strongly dominant matchings and show a linear time algorithm to solve the strongly dominant matching problem in a roommates instance. We consider a generalization of the max-size popular matching problem in bipartite graphs: this is the max-weight popular matching problem where there is also a weight function w : E → R and we seek a popular matching of largest weight. We show this is an NP-hard problem and this is so even when w(e) ∈ {1, 2} for every e ∈ E. We also show an algorithm with running time O * (2 n/4 ) to find a max-weight popular matching matching in G = (A ∪ B, E) on n vertices.
An efficient algorithm was also given in REF to compute a strongly dominant matching in a roommates instance.
Max-size popular matchings and extensions
ArXiv
ArXiv
Computer Science Mathematics