On the complexity of exchange-stable roommates

For the stable roommates problem recently a new concept, exchange stability, was introduced. In this paper we prove that it is NP-complete to decide whether for a given preference profile an exchange stable matching exists.