Polynomially tractable cases in the popular roommates problem

Erika Bérczi-Kovács, Ágnes Cseh, Kata Kosztolányi +1

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…