Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples

Gergely Csáji, David Manlove, Iain McBride +1

In this paper, we study the Hospitals / Residents problem with Couples (HRC), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time…