CS 537 talk on Tuesday, November 12 - Stable Roommates We will talk about the Stable Roommates problem. This time we don't have men and women - instead we have a group of people where each person ranks all others. That is, this time our graph is not bipartite. The goal is to find a stable matching. The plan for the lecture is the following: 1) the definition of the problem; examples. 2) Does the stable matching always exists? Example. 3) P or NP? How to find stable matching. Irving algorithm. Proposal phase and reduction phase. 4) How many stable matchings are there in a problem with random rankings? 5) How many problems have a solution? There is no particular reading assignment, but you need to go through the last lecture and recall things (such as GS algorithm and expected rankings of men and women), since there will be parallels.