Popular Matching in Roommates Setting is NP-hard

03/25/2018
by   Sushmita Gupta, et al.
0

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^ such that there is no matching M where more people are happier 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, explicitly asked over the last decade.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset