Popular Matching in Roommates Setting Is NP-hard
From MaRDI portal
Publication:5065631
DOI10.1145/3442354zbMath1495.68093arXiv1803.09370OpenAlexW3140823561MaRDI QIDQ5065631
Pranabendu Misra, Meirav Zehavi, Saket Saurabh, Sushmita Gupta
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)
Full work available at URL: https://arxiv.org/abs/1803.09370
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)
Related Items
Popular Branchings and Their Dual Certificates ⋮ Quasi-Popular Matchings, Optimality, and Extended Formulations ⋮ Popular matchings in complete graphs ⋮ Finding and Recognizing Popular Coalition Structures ⋮ Two problems in max-size popular matchings ⋮ On weakly and strongly popular rankings ⋮ Uncertain Measure and its Application in Minimum Weighted Maximal Matching Problem ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Unpopularity factor in the marriage and roommates problems ⋮ Popular Matchings in Complete Graphs ⋮ Popularity, Mixed Matchings, and Self-Duality ⋮ Understanding Popular Matchings via Stable Matchings ⋮ Popular branchings and their dual certificates
