Popular matchings in complete graphs
- Our input is a complete graph G 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 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 '} in which 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-complete for even n, as we show here. This is one of the few graph theoretic problems efficiently solvable when n has one parity and NP-complete when n has the other parity.
Author details: | Ágnes CsehORCiDGND, Telikepalli KavithaGND |
---|---|
DOI: | https://doi.org/10.1007/s00453-020-00791-7 |
ISSN: | 0178-4617 |
ISSN: | 1432-0541 |
Title of parent work (English): | Algorithmica : an international journal in computer science |
Publisher: | Springer |
Place of publishing: | New York |
Publication type: | Article |
Language: | English |
Date of first publication: | 2021/01/25 |
Publication year: | 2021 |
Release date: | 2024/05/23 |
Tag: | Complexity; Popular matching; Stable matching |
Volume: | 83 |
Issue: | 5 |
Number of pages: | 31 |
First page: | 1493 |
Last Page: | 1523 |
Funding institution: | ELKH Centre for Economic and Regional Studies |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |
5 Naturwissenschaften und Mathematik / 51 Mathematik / 510 Mathematik | |
Peer review: | Referiert |
Publishing method: | Open Access / Hybrid Open-Access |
License (German): | CC-BY - Namensnennung 4.0 International |