arbiter
JournalsPricingAccount

Polynomially tractable cases in the popular roommates problem

Erika Bérczi-Kovács et al.

Journal of Mechanism and Institution Design2025https://doi.org/10.22574/jmid.2025.12.003article
AJG 1
Weight
0.50

What the paper says

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 popular if there is no matching M' that is more popular than M. Faenza et al. (2019) and Gupta et al. (2021) proved that determining the existence of a popular matching in a popular roommates instance 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.

Open paper page →

Cite this paper

https://doi.org/https://doi.org/10.22574/jmid.2025.12.003

Or copy a formatted citation

@article{erika2025,
  title        = {{Polynomially tractable cases in the popular roommates problem}},
  author       = {Erika Bérczi-Kovács et al.},
  journal      = {Journal of Mechanism and Institution Design},
  year         = {2025},
  doi          = {https://doi.org/https://doi.org/10.22574/jmid.2025.12.003},
}

Paste directly into BibTeX, Zotero, or your reference manager.

Flag this paper

Polynomially tractable cases in the popular roommates problem

Flags are reviewed by the Arbiter methodology team within 5 business days.

Evidence weight

0.50

Balanced mode · F 0.40 / M 0.15 / V 0.05 / R 0.40

F · citation impact0.50 × 0.4 = 0.20
M · momentum0.50 × 0.15 = 0.07
V · venue signal0.50 × 0.05 = 0.03
R · text relevance †0.50 × 0.4 = 0.20

† Text relevance is estimated at 0.50 on the detail page — for your query’s actual relevance score, open this paper from a search result.