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.