Popular Matchings in Complete Graphs

Speaker: 

Ágnes Cseh

Affiliation: 

Hungarian Academy of Sciences

Date: 

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

Venue: 

RC-3085, The Red Centre, UNSW

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$. 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: