Document Open Access Logo

Popular Matchings in Complete Graphs

Authors Ágnes Cseh, Telikepalli Kavitha

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.17.pdf
  • Filesize: 449 kB
  • 14 pages

Document Identifiers

Author Details

Ágnes Cseh
  • Hungarian Academy of Sciences, Budapest, Hungary
Telikepalli Kavitha
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

  • Cseh, Ágnes: Supported by the Cooperation of Excellences Grant (KEP-6/2017), by the Ministry of Human Resources under its New National Excellence Programme (ÚNKP-18-4-BME-331), the Hungarian Academy of Sciences under its Momentum Programme (LP2016-3/2016), its János Bolyai Research Fellowship, and OTKA grant K128611.
  • Kavitha, Telikepalli: This work was done while visiting the Hungarian Academy of Sciences, Budapest.

Cite AsGet BibTex

Ágnes Cseh and Telikepalli Kavitha. Popular Matchings in Complete Graphs. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 17:1-17:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.FSTTCS.2018.17

Abstract

Our input is a complete graph G = (V,E) on n vertices where each vertex has a strict ranking of all other vertices in G. The goal is to construct a matching in G that is "globally stable" or popular. A matching M is popular if M does not lose a head-to-head election against any matching M': here each vertex casts a vote for the matching in {M,M'} where it gets a better assignment. Popular matchings need not exist in the given instance G and the popular matching problem is to decide whether one exists or not. The popular matching problem in G is easy to solve for odd n. Surprisingly, the problem becomes NP-hard for even n, as we show here.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • popular matching
  • complete graph
  • complexity
  • linear programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Condorcet method. Accessed 3 October 2018. URL: https://en.wikipedia.org/wiki/Condorcet_method.
  2. C.-C. Huang. Personal communication. Google Scholar
  3. P. Biró, R.W. Irving, and D.F. Manlove. Popular matchings in the Marriage and Roommates problems. In Proceedings of CIAC '10: the 7th International Conference on Algorithms and Complexity, volume 6078 of Lecture Notes in Computer Science, pages 97-108. Springer, 2010. Google Scholar
  4. P. Biró and E. McDermid. Three-sided stable matchings with cyclic preferences. Algorithmica, 58(1):5-18, 2010. Google Scholar
  5. K.S. Chung. On the Existence of Stable Roommate Matchings. Games and Economic Behavior, 33(2):206-230, 2000. Google Scholar
  6. M.-J.-A.-N. de C. (Marquis de) Condorcet. Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix. L'Imprimerie Royale, 1785. Google Scholar
  7. Ágnes Cseh. Popular matchings. Trends in Computational Social Choice, page 105, 2017. Google Scholar
  8. Ágnes Cseh and Telikepalli Kavitha. Popular edges and dominant matchings. Mathematical Programming, pages 1-21, 2017. online first. Google Scholar
  9. Ágnes Cseh and Telikepalli Kavitha. Popular Matchings in Complete Graphs. CoRR, abs/1807.01112, 2018. Google Scholar
  10. Yuri Faenza, Telikepalli Kavitha, Vladlena Powers, and Xingyu Zhang. Popular Matchings and Limits to Tractability. arXiv preprint arXiv:1805.11473, 2018. Google Scholar
  11. D. Gale and L.S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962. Google Scholar
  12. P. Gärdenfors. Match making: assignments based on bilateral preferences. Behavioural Science, 20:166-173, 1975. Google Scholar
  13. Sushmita Gupta, Pranabendu Misra, Saket Saurabh, and Meirav Zehavi. Popular Matching in Roommates Setting is NP-hard. arXiv preprint arXiv:1803.09370, 2018. Google Scholar
  14. C.-C. Huang and T. Kavitha. Popular Matchings in the Stable Marriage Problem. In Proceedings of ICALP '11: the 38th International Colloquium on Automata, Languages and Programming, volume 6755 of Lecture Notes in Computer Science, pages 666-677. Springer, 2011. Google Scholar
  15. C.-C. Huang and T. Kavitha. Near-popular matchings in the Roommates problem. SIAM Journal on Discrete Mathematics, 27(1):43-62, 2013. Google Scholar
  16. Chien-Chung Huang and Telikepalli Kavitha. Popularity, mixed matchings, and self-duality. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2294-2310. Society for Industrial and Applied Mathematics, 2017. Google Scholar
  17. R.W. Irving. An efficient algorithm for the "stable roommates" problem. Journal of Algorithms, 6:577-595, 1985. Google Scholar
  18. T. Kavitha, J. Mestre, and M. Nasre. Popular Mixed Matchings. In Proceedings of ICALP '09: the 36th International Colloquium on Automata, Languages and Programming, volume 5555 of Lecture Notes in Computer Science, pages 574-584. Springer, 2009. Google Scholar
  19. Telikepalli Kavitha. A size-popularity tradeoff in the stable marriage problem. SIAM Journal on Computing, 43(1):52-71, 2014. Google Scholar
  20. Telikepalli Kavitha. Popular half-integral matchings. In LIPIcs-Leibniz International Proceedings in Informatics, volume 55. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  21. Telikepalli Kavitha. Max-size popular matchings and extensions. arXiv preprint arXiv:1802.07440, 2018. Google Scholar
  22. David F. Manlove. Algorithmics of Matching Under Preferences, volume 2 of Series on Theoretical Computer Science. WorldScientific, 2013. URL: http://dx.doi.org/10.1142/8591.
  23. Thomas J Schaefer. The complexity of satisfiability problems. In Proceedings of the tenth annual ACM symposium on Theory of computing, pages 216-226. ACM, 1978. Google Scholar
  24. A. Subramanian. A New Approach to Stable Matching Problems. SIAM Journal on Computing, 23(4):671-700, 1994. Google Scholar
  25. J.J.M. Tan. A necessary and sufficient condition for the existence of a complete stable matching. Journal of Algorithms, 12:154-178, 1991. Google Scholar
  26. C.-P. Teo and J. Sethuraman. The geometry of fractional stable matchings and its applications. Mathematics of Operations Research, 23(4):874-891, 1998. Google Scholar
  27. Gerhard J Woeginger. Core stability in hedonic coalition formation. In International Conference on Current Trends in Theory and Practice of Computer Science, pages 33-50. Springer, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact