{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:16Z","timestamp":1740109336610,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T00:00:00Z","timestamp":1733788800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Supported by the Department of Atomic Energy, Government  of India","award":["project no. RTI4001"],"award-info":[{"award-number":["project no. RTI4001"]}]},{"DOI":"10.13039\/501100001405","name":"Tata Institute of Fundamental Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100001405","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2025,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>We consider the popular matching problem in a <jats:italic>roommates<\/jats:italic> instance <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices, i.e., <jats:italic>G<\/jats:italic> is a graph where each vertex has a strict preference order over its neighbors. A matching <jats:italic>M<\/jats:italic> is <jats:italic>popular<\/jats:italic> if there is no matching <jats:italic>N<\/jats:italic> such that the vertices that prefer <jats:italic>N<\/jats:italic> to <jats:italic>M<\/jats:italic> outnumber those that prefer <jats:italic>M<\/jats:italic> to\u00a0<jats:italic>N<\/jats:italic>. It is known that it is NP-hard to decide if <jats:italic>G<\/jats:italic> admits a popular matching or not.  There is no better algorithm known for this problem than the brute force algorithm that enumerates all matchings and tests each for popularity\u2014this could take <jats:italic>n<\/jats:italic>! time. Here we show an <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O^*(k^n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>\u2217<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mi>k<\/mml:mi>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time algorithm for this problem, where <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$k &lt; 7.32$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>7.32<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>. We use the recent breakthrough result on the maximum number of stable matchings possible in a roommates instance to analyze our algorithm for the popular matching problem. We identify a natural (also, hard) subclass of popular matchings called <jats:italic>truly popular<\/jats:italic> matchings that are \u201cpopular fractional\u201d and show an <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$O^*(2^n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mi>O<\/mml:mi>\n                      <mml:mo>\u2217<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:msup>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>n<\/mml:mi>\n                      <\/mml:msup>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> time algorithm for the truly popular matching problem in <jats:italic>G<\/jats:italic>. We also identify a subclass of max-size popular matchings called <jats:italic>super-dominant<\/jats:italic> matchings and show a linear time algorithm for the super-dominant roommates problem.<\/jats:p>","DOI":"10.1007\/s00453-024-01287-4","type":"journal-article","created":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T11:07:12Z","timestamp":1733828832000},"page":"292-320","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Popular Roommates in Simply Exponential Time"],"prefix":"10.1007","volume":"87","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2619-6606","authenticated-orcid":false,"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,12,10]]},"reference":[{"issue":"4","key":"1287_CR1","doi-asserted-by":"publisher","first-page":"1030","DOI":"10.1137\/06067328X","volume":"37","author":"DJ Abraham","year":"2007","unstructured":"Abraham, D.J., Irving, R.W., Kavitha, T., Mehlhorn, K.: Popular matchings. SIAM J. Comput. 37(4), 1030\u20131045 (2007)","journal-title":"SIAM J. Comput."},{"key":"1287_CR2","first-page":"253","volume":"12","author":"BL Balinski","year":"1965","unstructured":"Balinski, B.L.: Integer programming: methods, uses, computation. Manag. Sci. Ser. A 12, 253\u2013313 (1965)","journal-title":"Manag. Sci. Ser. A"},{"key":"1287_CR3","unstructured":"B\u00e9rczi-Kov\u00e1cs, E., Cseh, \u00c1., Kosztol\u00e1nyi, K., M\u00e1lyusz, A.: Polynomially tractable cases in the popular roommates problem. arxiv:2107.06694"},{"key":"1287_CR4","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Irving, R.W., Manlove, D.F.: Popular matchings in the marriage and roommates problems. In: Proceedings of the 7th International Conference on Algorithms and Complexity (CIAC), pp. 97\u2013108 (2010)","DOI":"10.1007\/978-3-642-13073-1_10"},{"issue":"7","key":"1287_CR5","doi-asserted-by":"publisher","first-page":"2738","DOI":"10.1007\/s00453-019-00553-0","volume":"81","author":"F Brandl","year":"2019","unstructured":"Brandl, F., Kavitha, T.: Two problems in max-size popular matchings. Algorithmica 81(7), 2738\u20132764 (2019)","journal-title":"Algorithmica"},{"issue":"2","key":"1287_CR6","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1006\/game.1999.0779","volume":"33","author":"K Chung","year":"2000","unstructured":"Chung, K.: On the existence of stable roommate matchings. Games Econ. Behav. 33(2), 206\u2013230 (2000)","journal-title":"Games Econ. Behav."},{"key":"1287_CR7","unstructured":"Condorcet method. https:\/\/en.wikipedia.org\/wiki\/Condorcet_method"},{"key":"1287_CR8","unstructured":"Cseh, \u00c1.: Popular matchings. Trends in Computational Social Choice, Ulle Endriss (ed.) (2017)"},{"issue":"4","key":"1287_CR9","doi-asserted-by":"publisher","first-page":"2348","DOI":"10.1137\/16M1076162","volume":"31","author":"\u00c1 Cseh","year":"2017","unstructured":"Cseh, \u00c1., Huang, C.-C., Kavitha, T.: Popular matchings with two-sided preferences and one-sided ties. SIAM J. Discret. Math. 31(4), 2348\u20132377 (2017)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"1287_CR10","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/s10107-017-1183-y","volume":"172","author":"\u00c1 Cseh","year":"2018","unstructured":"Cseh, \u00c1., Kavitha, T.: Popular edges and dominant matchings. Math. Program. 172(1), 209\u2013229 (2018)","journal-title":"Math. Program."},{"issue":"5","key":"1287_CR11","doi-asserted-by":"publisher","first-page":"1493","DOI":"10.1007\/s00453-020-00791-7","volume":"83","author":"A Cseh","year":"2021","unstructured":"Cseh, A., Kavitha, T.: Popular matchings in complete graphs. Algorithmica 83(5), 1493\u20131523 (2021)","journal-title":"Algorithmica"},{"key":"1287_CR12","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1007\/BFb0121194","volume":"8","author":"WH Cunningham","year":"1978","unstructured":"Cunningham, W.H., Marsh, A.B.: A primal algorithm for optimal matching. Math. Program. 8, 50\u201372 (1978)","journal-title":"Math. Program."},{"key":"1287_CR13","unstructured":"de\u00a0Condorcet, N.: Essai sur l\u2019application de l\u2019analyse \u00e0 la probabilit\u00e9 des d\u00e9cisions rendues \u00e0 la pluralit\u00e9 des voix. L\u2019Imprimerie Royale (1785)"},{"issue":"1","key":"1287_CR14","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00453-010-9416-y","volume":"58","author":"BC Dean","year":"2010","unstructured":"Dean, B.C., Munshi, S.: Faster algorithms for stable allocation problems. Algorithmica 58(1), 59\u201381 (2010)","journal-title":"Algorithmica"},{"key":"1287_CR15","doi-asserted-by":"publisher","first-page":"125","DOI":"10.6028\/jres.069B.013","volume":"69B","author":"J Edmonds","year":"1965","unstructured":"Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. B 69B, 125\u2013130 (1965)","journal-title":"J. Res. Natl. Bur. Stand. B"},{"key":"1287_CR16","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2790\u20132809 (2019)","DOI":"10.1137\/1.9781611975482.173"},{"key":"1287_CR17","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.tcs.2007.04.029","volume":"381","author":"T Fleiner","year":"2007","unstructured":"Fleiner, T., Irving, R.W., Manlove, D.F.: Efficient algorithms for generalised stable marriage and roommates problems. Theor. Comput. Sci. 381, 162\u2013176 (2007)","journal-title":"Theor. Comput. Sci."},{"key":"1287_CR18","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16533-7","volume-title":"Exact exponential algorithms","author":"FV Fomin","year":"2010","unstructured":"Fomin, F.V., Kratsch, D.: Exact exponential algorithms. Springer-Verlag, New York Inc, New York (2010)"},{"issue":"1","key":"1287_CR19","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1080\/00029890.1962.11989827","volume":"69","author":"D Gale","year":"1962","unstructured":"Gale, D., Shapley, L.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"issue":"3","key":"1287_CR20","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1002\/bs.3830200304","volume":"20","author":"P G\u00e4rdenfors","year":"1975","unstructured":"G\u00e4rdenfors, P.: Match making: assignments based on bilateral preferences. Behav. Sci. 20(3), 166\u2013173 (1975)","journal-title":"Behav. Sci."},{"issue":"2","key":"1287_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3442354","volume":"13","author":"S Gupta","year":"2021","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP hard. ACM Trans. Comput. Theor. 13(2), 1\u201320 (2021)","journal-title":"ACM Trans. Comput. Theor."},{"key":"1287_CR22","volume-title":"The stable marriage problem: structure and algorithms","author":"D Gusfield","year":"1989","unstructured":"Gusfield, D., Irving, R.W.: The stable marriage problem: structure and algorithms. MIT Press, Boston, MA (1989)"},{"key":"1287_CR23","unstructured":"Hirakawa, M., Yamauchi, Y., Kijima, S., Yamashita, M.: On the structure of popular matchings in the stable marriage problem\u2014 Who Can Join a Popular Matching? In the 3rd International Workshop on Matching Under Preferences (MATCH-UP) (2015)"},{"issue":"1","key":"1287_CR24","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1137\/110852838","volume":"27","author":"C-C Huang","year":"2013","unstructured":"Huang, C.-C., Kavitha, T.: Near-popular matchings in the roommates problem. SIAM J. Discret. Math. 27(1), 43\u201362 (2013)","journal-title":"SIAM J. Discret. Math."},{"key":"1287_CR25","doi-asserted-by":"publisher","first-page":"180","DOI":"10.1016\/j.ic.2012.10.012","volume":"222","author":"C-C Huang","year":"2013","unstructured":"Huang, C.-C., Kavitha, T.: Popular matchings in the stable marriage problem. Inform. Comput. 222, 180\u2013194 (2013)","journal-title":"Inform. Comput."},{"issue":"2","key":"1287_CR26","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1287\/moor.2020.1063","volume":"46","author":"C-C Huang","year":"2021","unstructured":"Huang, C.-C., Kavitha, T.: Popularity, mixed matchings, and self-duality. Math. Op. Res. 46(2), 405\u2013427 (2021)","journal-title":"Math. Op. Res."},{"key":"1287_CR27","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","volume":"6","author":"R Irving","year":"1985","unstructured":"Irving, R.: An efficient algorithm for the stable roommates problem. J. Algorithms 6, 577\u2013595 (1985)","journal-title":"J. Algorithms"},{"key":"1287_CR28","doi-asserted-by":"crossref","unstructured":"Karlin, A.R., Gharan, S.O., Weber, R.: A simply exponential upper bound on the maximum number of stable matchings. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 920\u2013925, (2018)","DOI":"10.1145\/3188745.3188848"},{"key":"1287_CR29","unstructured":"Kavitha, T.: Max-size popular matchings and extensions. arxiv:1802.07440"},{"issue":"1","key":"1287_CR30","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1137\/120902562","volume":"43","author":"T Kavitha","year":"2014","unstructured":"Kavitha, T.: A size-popularity tradeoff in the stable marriage problem. SIAM J. Comput. 43(1), 52\u201371 (2014)","journal-title":"SIAM J. Comput."},{"key":"1287_CR31","unstructured":"Kavitha, T.: Popular half-integral matchings. In: Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp. 22.1\u201322.13 (2016)"},{"key":"1287_CR32","unstructured":"Kavitha, T.: Popular roommates in simply exponential time. In: Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019), pp. 20.1\u201320.15 (2019)"},{"key":"1287_CR33","unstructured":"Kavitha, T.: Min-cost popular matchings. In: Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020), pp. 25.1\u201325.17 (2020)"},{"key":"1287_CR34","unstructured":"Kavitha, T.: Maximum matchings and popularity. In: Proceedings of the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), pp. 85:1\u201385:21 (2021)"},{"key":"1287_CR35","doi-asserted-by":"crossref","unstructured":"Kavitha, T., Kir\u00e1ly, T., Matuschke, J., Schlotter, I., Schmidt-Kraepelin, U.: The popular assignment problem: when cardinality is more important than popularity. In: SODA 2022: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 103\u2013123, SIAM (2022)","DOI":"10.1137\/1.9781611977073.6"},{"issue":"24","key":"1287_CR36","doi-asserted-by":"publisher","first-page":"2679","DOI":"10.1016\/j.tcs.2010.03.028","volume":"412","author":"T Kavitha","year":"2011","unstructured":"Kavitha, T., Mestre, J., Nasre, M.: Popular mixed matchings. Theor. Comput. Sci. 412(24), 2679\u20132690 (2011)","journal-title":"Theor. Comput. Sci."},{"key":"1287_CR37","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1007\/s00453-012-9672-0","volume":"68","author":"E McDermid","year":"2014","unstructured":"McDermid, E., Irving, R.W.: Sex-equal stable matchings: Complexity and exact algorithms. Algorithmica 68, 545\u2013570 (2014)","journal-title":"Algorithmica"},{"key":"1287_CR38","unstructured":"Palmer, C., P\u00e1lv\u00f6lgyi, D.: At most $$3.55^n$$ stable matchings. In: Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 221\u2013227 (2021)"},{"issue":"3","key":"1287_CR39","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1007\/s00182-007-0083-4","volume":"36","author":"N Perach","year":"2008","unstructured":"Perach, N., Polak, J., Rothblum, U.: A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion. Int. J. Game Theor. 36(3), 519\u2013535 (2008)","journal-title":"Int. J. Game Theor."},{"issue":"4","key":"1287_CR40","doi-asserted-by":"publisher","first-page":"671","DOI":"10.1137\/S0097539789169483","volume":"23","author":"A Subramanian","year":"1994","unstructured":"Subramanian, A.: A new approach to stable matching problems. SIAM J. Comput. 23(4), 671\u2013700 (1994)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1287_CR41","doi-asserted-by":"publisher","first-page":"874","DOI":"10.1287\/moor.23.4.874","volume":"23","author":"C-P Teo","year":"1998","unstructured":"Teo, C.-P., Sethuraman, J.: The geometry of fractional stable matchings and its applications. Math. Op. Res. 23(4), 874\u2013891 (1998)","journal-title":"Math. Op. Res."},{"issue":"1\u20133","key":"1287_CR42","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1016\/S0012-365X(01)00194-7","volume":"248","author":"EG Thurber","year":"2002","unstructured":"Thurber, E.G.: Concerning the maximum number of stable matchings in the stable marriage problem. Discre. Math. 248(1\u20133), 195\u2013219 (2002)","journal-title":"Discre. Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01287-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-024-01287-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-024-01287-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,12]],"date-time":"2025-02-12T23:14:59Z","timestamp":1739402099000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-024-01287-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,12,10]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2]]}},"alternative-id":["1287"],"URL":"https:\/\/doi.org\/10.1007\/s00453-024-01287-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2024,12,10]]},"assertion":[{"value":"22 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 December 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no competing financial or non-financial interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}