|
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'$ 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 \emph{popular} if there is no matching~$M'$ that is more popular than~$M$.
Only recently Faenza et al.~\cite{FKPZ19} and Gupta et al.~\cite{GMSZ21} 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.
Bibtex entry:
| AUTHOR | = | {B{\'e}rczi-Kov{\'a}cs Ren{\'a}ta, Erika and Cseh, Ágnes and Kosztol{\'a}nyi, Kata and M{\'a}lyusz Edmund, Attila}, |
| TITLE | = | {Polynomially tractable cases in the popular roommates problem}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-10} |