TY  - JOUR
A1  - Cseh, Ágnes
A1  - Kavitha, Telikepalli
T1  - Popular matchings in complete graphs
T2  - Algorithmica : an international journal in computer science
N2  - 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.
KW  - Popular matching
KW  - Complexity
KW  - Stable matching
Y1  - 2021
UR  - https://publishup.uni-potsdam.de/frontdoor/index/index/docId/63683
SN  - 0178-4617
SN  - 1432-0541
VL  - 83
IS  - 5
SP  - 1493
EP  - 1523
PB  - Springer
CY  - New York
ER  -