Popular Matching in Roommates Setting Is NP-hard

DOI10.1145/3442354zbMath1495.68093arXiv1803.09370MaRDI QIDQ5065631

Meirav Zehavi, Saket Saurabh, Pranabendu Misra, 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

zbMATH Keywords

NP-hardness; popular matching

Mathematics Subject Classification ID

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91B68: Matching models