The Stable Roommates Problem (SR) was first introduced by Gale and Shapley [1]}. They noted that unlike the related stable marriage problem, SR does not always admit a stable matching. An instance where that happens is in Figure REF . If we match the pairs \(\lbrace a_1, a_2\rbrace \)  and \(\lbrace a_3, a_4\rbrace \) , \(a_2\)  and \(a_3\)  prefer each other to their assigned partners. Similarly, if we match \(\lbrace a_1, a_3\rbrace \)  and \(\lbrace a_2, a_4\rbrace \)  \(a_1\)  and \(a_2\)  prefer each other to their assigned partners, and if we match \(\lbrace a_2, a_3\rbrace \)  and \(\lbrace a_1, a_4\rbrace \) , then \(a_1\)  and \(a_3\)  block the matching.
