Structural and Algorithmic Results for Stable Cycles and Partitions in the Roommates Problem

Frederik Glitzner, David Manlove

In the Stable Roommates problem, we seek a stable matching of the agents into pairs, in which no two agents have an incentive to deviate from their assignment. It is well known tha…