A Quadratic Lower Bound for Stable Roommates Solvability

Will Rosenbaum

In their seminal work on the Stable Marriage Problem (SM), Gale and Shapley introduced a generalization of SM referred to as the Stable Roommates Problem (SR). An instance of SR co…