Popular matching in roommates setting is NP-hard

DOI10.1145/3442354zbMATH Open1495.68093arXiv1803.09370OpenAlexW3140823561WikidataQ130949707 ScholiaQ130949707MaRDI QIDQ5065631FDOQ5065631

Authors: Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi 

Publication date: 22 March 2022

Published in: ACM Transactions on Computation Theory, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: An input to the Popular Matching problem, in the roommates setting, consists of a graph $G$ and each vertex ranks its neighbors in strict order, known as its preference. In the Popular Matching problem the objective is to test whether there exists a matching $M^{s}tar$ such that there is no matching $M$ where more people are happier with $M$ than with $M^{s}tar$. In this paper we settle the computational complexity of the Popular Matching problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly, explicitly asked over the last decade.

Full work available at URL: https://arxiv.org/abs/1803.09370

Recommendations

• Popular matching in roommates setting is NP-hard
• Popular matching in roommates setting is \textsf{NP}-hard
• Near-popular matchings in the roommates problem
• Near-popular matchings in the roommates problem
• Popular matchings in the marriage and roommates problems

zbMATH Keywords

NP-hardnesspopular matching

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Cited In (24)

• Popular Matchings in Complete Graphs
• Finding and Recognizing Popular Coalition Structures
• Uncertain measure and its application in minimum weighted maximal matching problem
• Understanding popular matchings via stable matchings
• Popular branchings and their dual certificates
• Solving the maximum popular matching problem with matroid constraints
• Finding strongly popular \(b\)-matchings in bipartite graphs
• Near-popular matchings in the roommates problem
• Popularity, Mixed Matchings, and Self-Duality
• Popularity on the roommate diversity problem
• Near-popular matchings in the roommates problem
• Popular matching in roommates setting is NP-hard
• Unpopularity factor in the marriage and roommates problems
• Quasi-popular matchings, optimality, and extended formulations
• Popular matchings in complete graphs
• On weakly and strongly popular rankings
• Popular branchings and their dual certificates
• Popularity on the roommate diversity problem
• Popular matchings with weighted voters
• NP-complete stable matching problems
• Popular matching in roommates setting is \textsf{NP}-hard
• Two problems in max-size popular matchings
• Computational complexity of \(k\)-stable matchings
• Stable matchings, one-sided ties, and approximate popularity

This page was built for publication: Popular matching in roommates setting is NP-hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065631)