Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals / Residents Problem with Couples

We describe a novel polynomial-time algorithm for the Hospitals / Residents problem with Couples (HRC) that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) when couples' preferences are responsive (i.e., if one member switches to a better hospital, than the couple also improves) and subcomplete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing to an instance of the Stable Fixtures problem.

We also present a new polynomial-time algorithm for HRC in a responsive, subcomplete instance that is a Dual Market, or where all couples are one of several possible types. We also describe several hardness results. We show that HRC with responsive and subcomplete couples is NP-hard, even with other strong restrictions. We also show that HRC with a Dual Market is NP-hard under several simultaneous restrictions. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in HRC is very hard to approximate, even if each couple applies to only one pair of hospitals.

Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC and provide strong evidence as to why long-standing entry-level labour markets that allow couples such as the National Resident Matching Program remain successful to this day. This is joint work with Gergely Csáji, Iain McBride and James Trimble.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.