Polynomially tractable cases in the popular roommates problem

Abstract

The input of the popular roommates problem consists of a graph $G=(V,E)$ and for each vertex $v\in V$, strict preferences over the neighbors of $v$. Matching $M$ is more popular than $M^{\prime }$ if the number of vertices preferring $M$ to $M^{\prime }$ is larger than the number of vertices preferring $M^{\prime }$ to $M$. A matching $M$ is called popular if there is no matching $M^{\prime }$ 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.