Popular Matchings in Complete Graphs


Ágnes Cseh


Hungarian Academy of Sciences


Wed, 24/04/2019 - 12:00pm


RC-3085, The Red Centre, UNSW


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$. Our 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'$, where each vertex casts a vote for the matching in $\{M,M'\}$ where it gets assigned a better partner. The popular matching problem is to decide whether a popular matching 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$. Joint work with T. Kavitha.

School Seminar Series: