{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:50:03Z","timestamp":1759063803072,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T00:00:00Z","timestamp":1611532800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T00:00:00Z","timestamp":1611532800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003825","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia","doi-asserted-by":"publisher","award":["LP2016-3\/2016"],"award-info":[{"award-number":["LP2016-3\/2016"]}],"id":[{"id":"10.13039\/501100003825","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007626","name":"Magyar Tudom\u00e1nyos Akad\u00e9mia Sz\u00e1m\u00edt\u00e1stechnikai\u00e9s Automatiz\u00e1l\u00e1si Kutat\u00f3int\u00e9zet","doi-asserted-by":"publisher","award":["K128611"],"award-info":[{"award-number":["K128611"]}],"id":[{"id":"10.13039\/100007626","id-type":"DOI","asserted-by":"publisher"}]},{"name":"ELKH Centre for Economic and Regional Studies"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Our input is a complete graph <jats:italic>G<\/jats:italic> on <jats:italic>n<\/jats:italic> vertices where each vertex has a strict ranking of all other vertices in <jats:italic>G<\/jats:italic>. The goal is to construct a matching in <jats:italic>G<\/jats:italic> that is <jats:italic>popular<\/jats:italic>. A matching <jats:italic>M<\/jats:italic> is popular if <jats:italic>M<\/jats:italic> does not lose a head-to-head election against any matching <jats:inline-formula><jats:alternatives><jats:tex-math>$$M'$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mo>\u2032<\/mml:mo>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>: here each vertex casts a vote for the matching in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\{M,M'\\}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mo>{<\/mml:mo>\n                    <mml:mi>M<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>M<\/mml:mi>\n                      <mml:mo>\u2032<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mo>}<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> in which it gets a better assignment. Popular matchings need not exist in the given instance <jats:italic>G<\/jats:italic> and the popular matching problem is to decide whether one exists or not. The popular matching problem in <jats:italic>G<\/jats:italic> is easy to solve for odd\u00a0<jats:italic>n<\/jats:italic>. Surprisingly, the problem becomes <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\texttt {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete for even <jats:italic>n<\/jats:italic>, as we show here. This is one of the few graph theoretic problems efficiently solvable when <jats:italic>n<\/jats:italic> has one parity and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\texttt {NP}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>NP<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-complete when <jats:italic>n<\/jats:italic> has the other parity.<\/jats:p>","DOI":"10.1007\/s00453-020-00791-7","type":"journal-article","created":{"date-parts":[[2021,1,25]],"date-time":"2021-01-25T15:05:04Z","timestamp":1611587104000},"page":"1493-1523","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Popular Matchings in Complete Graphs"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4991-2599","authenticated-orcid":false,"given":"\u00c1gnes","family":"Cseh","sequence":"first","affiliation":[]},{"given":"Telikepalli","family":"Kavitha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,1,25]]},"reference":[{"key":"791_CR1","doi-asserted-by":"crossref","unstructured":"Bir\u00f3, P., Irving, R. W., Manlove, D.: 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":"1","key":"791_CR2","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1007\/s00453-009-9315-2","volume":"58","author":"P Bir\u00f3","year":"2010","unstructured":"Bir\u00f3, P., McDermid, E.: Three-sided stable matchings with cyclic preferences. Algorithmica 58(1), 5\u201318 (2010)","journal-title":"Algorithmica"},{"issue":"7","key":"791_CR3","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":"791_CR4","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1006\/game.1999.0779","volume":"33","author":"KS Chung","year":"2000","unstructured":"Chung, K.S.: On the existence of stable roommate matchings. Games Econ Behav 33(2), 206\u2013230 (2000)","journal-title":"Games Econ Behav"},{"key":"791_CR5","unstructured":"de Condorcet (Marquis de) M-J-A-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)"},{"key":"791_CR6","unstructured":"Condorcet method. https:\/\/en.wikipedia.org\/wiki\/Condorcet_method"},{"key":"791_CR7","unstructured":"Cseh, \u00c1.: Popular matchings. In: Endriss U (Ed) Trends in computational social choice, COST (European Cooperation in Science and Technology), pp. 105\u2013122 (2017)"},{"issue":"1","key":"791_CR8","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."},{"key":"791_CR9","unstructured":"Cseh, \u00c1., Kavitha, T.: Popular matchings in complete graphs. In: 38th Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 17:1\u201317:14 (2018)"},{"key":"791_CR10","doi-asserted-by":"crossref","unstructured":"Faenza, Y.: Kavitha, T.: Quasi-popular matchings, optimality, and extended formulations. In: 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), 325-344 (2020)","DOI":"10.1137\/1.9781611975994.20"},{"key":"791_CR11","doi-asserted-by":"crossref","unstructured":"Faenza, Y., Kavitha, T., Powers, V., Zhang, X.: Popular matchings and limits to tractability. In: 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2790\u20132809 (2019)","DOI":"10.1137\/1.9781611975482.173"},{"key":"791_CR12","doi-asserted-by":"publisher","DOI":"10.4337\/9781840647761","volume-title":"The Measurement of Voting Power","author":"D Felsenthal","year":"1998","unstructured":"Felsenthal, D., Machover, M.: The Measurement of Voting Power. Edward Elgar Publishing, Cheltenham (1998)"},{"issue":"1","key":"791_CR13","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.S.: College admissions and the stability of marriage. Am. Math. Mon. 69(1), 9\u201315 (1962)","journal-title":"Am. Math. Mon."},{"key":"791_CR14","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, 166\u2013173 (1975)","journal-title":"Behav. Sci."},{"key":"791_CR15","doi-asserted-by":"crossref","unstructured":"Gupta, S., Misra, P., Saurabh, S., Zehavi, M.: Popular matching in roommates setting is NP-hard. In: 30th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2810\u20132822 (2019)","DOI":"10.1137\/1.9781611975482.174"},{"key":"791_CR16","unstructured":"Huang, C.-C.: Personal communication"},{"key":"791_CR17","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. Inf. Comput. 222, 180\u2013194 (2013)","journal-title":"Inf. Comput."},{"issue":"1","key":"791_CR18","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. Discrete Math. 27(1), 43\u201362 (2013)","journal-title":"SIAM J. Discrete Math."},{"key":"791_CR19","doi-asserted-by":"crossref","unstructured":"Huang, C.-C., Kavitha, T.: Popularity, mixed matchings, and self-duality. In: 28th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2294-2310 (2017)","DOI":"10.1137\/1.9781611974782.151"},{"key":"791_CR20","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1016\/0196-6774(85)90033-1","volume":"6","author":"RW Irving","year":"1985","unstructured":"Irving, R.W.: An efficient algorithm for the \u201cstable roommates\u201d problem. J. Algorithms 6, 577\u2013595 (1985)","journal-title":"J. Algorithms"},{"issue":"1","key":"791_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0097-3165(95)90115-9","volume":"69","author":"JC Janssen","year":"1995","unstructured":"Janssen, J.C.: On even and odd Latin squares. J. Comb. Theory Ser. A 69(1), 173\u2013181 (1995)","journal-title":"J. Comb. Theory Ser. A"},{"issue":"24","key":"791_CR22","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."},{"issue":"1","key":"791_CR23","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":"791_CR24","unstructured":"Kavitha, T.: Popular half-integral matchings. In: 43rd International Colloquium on Automata, Languages, and Programming (ICALP), pp 22.1\u201322.13 (2016)"},{"key":"791_CR25","unstructured":"Kavitha, T.: Max-size popular matchings and extensions. arXiv preprint arXiv:1802.07440 (2018)"},{"key":"791_CR26","doi-asserted-by":"crossref","unstructured":"Lam, C.\u00a0K., Plaxton., C.\u00a0G.: On the existence of three-dimensional stable matchings with cyclic preferences. In: 12th International Symposium on Algorithmic Game Theory (SAGT), pp. 329\u2013342 (2019)","DOI":"10.1007\/978-3-030-30473-7_22"},{"key":"791_CR27","doi-asserted-by":"publisher","DOI":"10.1142\/8591","volume-title":"Algorithmics of Matching Under Preferences","author":"DF Manlove","year":"2013","unstructured":"Manlove, D.F.: Algorithmics of Matching Under Preferences. World Scientific, Singapore (2013)"},{"key":"791_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T.J.: The complexity of satisfiability problems. In: 10th Annual ACM Symposium on Theory of Computing, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"},{"issue":"4","key":"791_CR29","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."},{"key":"791_CR30","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0196-6774(91)90028-W","volume":"12","author":"JJM Tan","year":"1991","unstructured":"Tan, J.J.M.: A necessary and sufficient condition for the existence of a complete stable matching. J. Algorithms 12, 154\u2013178 (1991)","journal-title":"J. Algorithms"},{"issue":"4","key":"791_CR31","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. Oper. Res. 23(4), 874\u2013891 (1998)","journal-title":"Math. Oper. Res."},{"key":"791_CR32","doi-asserted-by":"crossref","unstructured":"Woeginger, G.J.: Core stability in hedonic coalition formation. In: International Conference on Current Trends in Theory and Practice of Computer Science, pp. 33\u201350 (2013)","DOI":"10.1007\/978-3-642-35843-2_4"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00791-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00791-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00791-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,8]],"date-time":"2021-04-08T10:21:25Z","timestamp":1617877285000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00791-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,25]]},"references-count":32,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["791"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00791-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,1,25]]},"assertion":[{"value":"9 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 December 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 January 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}