{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:07:23Z","timestamp":1777540043149,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T00:00:00Z","timestamp":1616716800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100010661","name":"Horizon 2020 Framework Programme","doi-asserted-by":"publisher","award":["819416"],"award-info":[{"award-number":["819416"]}],"id":[{"id":"10.13039\/100010661","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            An input to the P\n            <jats:sc>OPULAR<\/jats:sc>\n            M\n            <jats:sc>ATCHING<\/jats:sc>\n            problem, in the roommates setting (as opposed to the marriage setting), consists of a graph\n            <jats:italic>G<\/jats:italic>\n            (not necessarily bipartite) where each vertex ranks its neighbors in strict order, known as its preference. In the P\n            <jats:sc>OPULAR<\/jats:sc>\n            M\n            <jats:sc>ATCHING<\/jats:sc>\n            problem the objective is to\n            <jats:italic>test<\/jats:italic>\n            whether there exists a matching\n            <jats:italic>M<\/jats:italic>\n            * such that there is no matching\n            <jats:italic>M<\/jats:italic>\n            where more vertices prefer their matched status in\n            <jats:italic>M<\/jats:italic>\n            (in terms of their preferences) over their matched status in\n            <jats:italic>M<\/jats:italic>\n            *. In this article, we settle the computational complexity of the P\n            <jats:sc>OPULAR<\/jats:sc>\n            M\n            <jats:sc>ATCHING<\/jats:sc>\n            problem in the roommates setting by showing that the problem is NP-complete. Thus, we resolve an open question that has been repeatedly and explicitly asked over the last decade.\n          <\/jats:p>","DOI":"10.1145\/3442354","type":"journal-article","created":{"date-parts":[[2021,3,26]],"date-time":"2021-03-26T16:31:02Z","timestamp":1616776262000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Popular Matching in Roommates Setting Is NP-hard"],"prefix":"10.1145","volume":"13","author":[{"given":"Sushmita","family":"Gupta","sequence":"first","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI, India"}]},{"given":"Pranabendu","family":"Misra","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics, Germany"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI, India and University of Bergen, Norway"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Israel"}]}],"member":"320","published-online":{"date-parts":[[2021,3,26]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905)","author":"Abraham D. J.","unstructured":"D. J. Abraham , R. W. Irving , T. Kavitha , and K. Mehlhorn . 2005. Popular matchings . In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905) . ACM-SIAM, 424--432. https:\/\/dl.acm.org\/doi\/10.5555\/1070432.1070491. D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. 2005. Popular matchings. In Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA\u201905). ACM-SIAM, 424--432. https:\/\/dl.acm.org\/doi\/10.5555\/1070432.1070491."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/06067328X"},{"key":"e_1_2_1_3_1","volume-title":"Manlove","author":"Bir\u00f3 P\u00e9ter","year":"2010","unstructured":"P\u00e9ter Bir\u00f3 , Robert W. Irving , and David F . Manlove . 2010 . Popular matchings in the marriage and roommates problems. In Algorithms and Complexity, Tiziana Calamoneri and Josep Diaz (Eds.). Springer , Berlin, 97--108. P\u00e9ter Bir\u00f3, Robert W. Irving, and David F. Manlove. 2010. Popular matchings in the marriage and roommates problems. In Algorithms and Complexity, Tiziana Calamoneri and Josep Diaz (Eds.). Springer, Berlin, 97--108."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1006\/game.1999.0779"},{"key":"e_1_2_1_5_1","unstructured":"Agnes Cseh. 2015. Popular matchings. (2015). Combinatorial Optimization Hausdorff Trimester Program. Retrieved from http:\/\/www.him.uni-bonn.de\/combinatorial-optimization-2015\/.  Agnes Cseh. 2015. Popular matchings. (2015). Combinatorial Optimization Hausdorff Trimester Program. Retrieved from http:\/\/www.him.uni-bonn.de\/combinatorial-optimization-2015\/."},{"key":"e_1_2_1_6_1","first-page":"105","article-title":"Popular matchings","volume":"105","author":"Cseh \u00c1gnes","year":"2017","unstructured":"\u00c1gnes Cseh . 2017 . Popular matchings . Trends Comput. Soc. Choice 105 , 3 (2017), 105 -- 122 . \u00c1gnes Cseh. 2017. Popular matchings. Trends Comput. Soc. Choice 105, 3 (2017), 105--122.","journal-title":"Trends Comput. Soc. Choice"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1076162"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-33461-5_12"},{"key":"e_1_2_1_9_1","unstructured":"M.-J.-A.-N. de C. (Marquis de) Condorcet. 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. De l\u2019Imprimerie royale M. DCCLXXXV.  M.-J.-A.-N. de C. (Marquis de) Condorcet. 1785. Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. De l\u2019Imprimerie royale M. DCCLXXXV."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.173"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1962.11989827"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/bs.3830200304"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.174"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/110852838"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2012.10.012"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69903-3_13"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.151"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/120902562"},{"key":"e_1_2_1_19_1","unstructured":"Telikepalli Kavitha. 2018. Max-size popular matchings and extensions. arXiv:1802.07440v1.  Telikepalli Kavitha. 2018. Max-size popular matchings and extensions. arXiv:1802.07440v1."},{"key":"e_1_2_1_20_1","unstructured":"Telikepalli Kavitha. 2018. The popular roommates problem. arXiv:1804.00141v2.  Telikepalli Kavitha. 2018. The popular roommates problem. arXiv:1804.00141v2."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.03.028"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2009.06.004"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10631-6_44"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2020.103105"},{"key":"e_1_2_1_25_1","volume-title":"Budapest","author":"Manlove David","year":"2013","unstructured":"David Manlove . 2013. The House Allocation problem (with applications to reviewer assignment). (2013). Summer School on Matching Problems, Markets, and Mechanisms , Budapest 2013 . Retrieved from http:\/\/econ.core.hu\/english\/res\/MatchingSchool.html. David Manlove. 2013. The House Allocation problem (with applications to reviewer assignment). (2013). Summer School on Matching Problems, Markets, and Mechanisms, Budapest 2013. Retrieved from http:\/\/econ.core.hu\/english\/res\/MatchingSchool.html."},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the14th Annual European Symposium (ESA\u201906)","author":"Manlove David","unstructured":"David Manlove and Colin T. S. Sng . 2006. Popular matchings in the capacitated house allocation problem . In Proceedings of the14th Annual European Symposium (ESA\u201906) . Springer, Berlin, 492--503. David Manlove and Colin T. S. Sng. 2006. Popular matchings in the capacitated house allocation problem. In Proceedings of the14th Annual European Symposium (ESA\u201906). Springer, Berlin, 492--503."},{"key":"e_1_2_1_27_1","volume-title":"Algorithmics of Matching Under Preferences. Theoretical Computer Science","author":"Manlove David F.","unstructured":"David F. Manlove . 2013. Algorithmics of Matching Under Preferences. Theoretical Computer Science , Vol. 2 . World Scientific . David F. Manlove. 2013. Algorithmics of Matching Under Preferences. Theoretical Computer Science, Vol. 2. World Scientific."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78773-0_51"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913160"},{"key":"e_1_2_1_30_1","unstructured":"Michael Sipser. 2006. Introduction to the Theory of Computation. Thomson Course Technology.  Michael Sipser. 2006. Introduction to the Theory of Computation. Thomson Course Technology."},{"key":"e_1_2_1_31_1","unstructured":"Egres Open Wiki. 2019. Deciding the existence of popular matchings. Retrieved from http:\/\/lemon.cs.elte.hu\/egres\/open\/Deciding_the_existence_of_popular_matchings.  Egres Open Wiki. 2019. Deciding the existence of popular matchings. Retrieved from http:\/\/lemon.cs.elte.hu\/egres\/open\/Deciding_the_existence_of_popular_matchings."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TWC.2015.2477077"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442354","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442354","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:21Z","timestamp":1750195461000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442354"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,26]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442354"],"URL":"https:\/\/doi.org\/10.1145\/3442354","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,26]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-03-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}