2021/07/14 by Bérczi-Kovács, Erika, Cseh, Ágnes, Kosztolányi, Kata +1
#Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2107.06694
The input of the popular roommates problem consists of a graph G = (V, E) and for each vertex v∈ V, strict preferences over the neighbors of v. Matching M is more popular than M' if the number of vertices preferring M to M' is larger than the number of vertices preferring M' to M. A matching M is called popular if there is no matching M' that is more popular than M. Only recently Faenza et al. and Gupta et al. resolved the long-standing open question on the complexity of deciding whether a popular matching exists in a popular roommates instance and showed that the problem is NP-complete. In this paper we identify a class of instances that admit a polynomial-time algorithm for the problem. We also test these theoretical findings on randomly generated instances to determine the existence probability of a popular matching in them.