Bridging the Gap Between Stable Marriage and Stable Roommates: A Parameterized Algorithm for Optimal Stable Matchings

Christine T. Cheng, Will Rosenbaum

In the Stable Roommates Problem (SR), a set of $2n$ agents rank one another in a linear order. The goal is to find a matching that is stable: one that has no pair of agents who mut…