Popular Matching in Roommates Setting is NP-hard

Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi


An input to the Popular Matching problem, in the roommates setting, consists of a graph G where 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⋆ such that there is no matching M where more people (vertices) are happier (in terms of the preferences) with M than with M⋆. 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 asked over the last decade.

Full Text:



  • There are currently no refbacks.