Popular Matchings in Complete Graphs

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^{\prime }$, where each vertex casts a vote for the matching in $\{M,M^{\prime }\}$ 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$, as we show here.

Appeared at FSTTCS 2018