Polynomially tractable cases in the popular roommates problem

Erika Bérczi-Kovács (), Ágnes Cseh (), Kata Kosztolányi () and Attila Mályusz ()
Additional contact information
Erika Bérczi-Kovács: Eötvös Loránd University, Hungary
Ágnes Cseh: University of Bayreuth, Germany
Kata Kosztolányi: Eötvös Loránd University, Hungary
Attila Mályusz: University of Freiburg, Germany

The Journal of Mechanism and Institution Design, 2025, vol. 10, issue 1, 67-95

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' 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.

Keywords: Popular matching; stable matching; complexity. (search for similar items in EconPapers)
JEL-codes: C63 C78 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mechanism-design.org/arch/v010-1/p_03.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jmi:articl:jmi-v10i1a3

DOI: 10.22574/jmid.2025.12.003

Access Statistics for this article

More articles in The Journal of Mechanism and Institution Design from Society for the Promotion of Mechanism and Institution Design, University of York Contact information at EDIRC.
Bibliographic data for series maintained by Paul Schweinzer ().