Popular Matching in Roommates Setting is NP-hard

Abstract

An input to the Popular Matching problem, in the roommates setting, consists of a graph $G$ and each vertex ranks its neighbors in strict order, known as its preference. In the Popular Matching problem the objective is to test whether there exists a matching $M^{\star }$ such that there is no matching $M$ where more people are happier with $M$ than with $M^{\star }$. In this paper we settle the computational complexity of the Popular Matching problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly, explicitly asked over the last decade.

20 pages, 7 figures