Popular Matching in Roommates Setting is NP-hard
2020
An input to the P opular M atching 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 P opular M atching 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 P opular M atching 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI