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 |
