<XML><RECORDS><RECORD><REFERENCE_TYPE>0</REFERENCE_TYPE><REFNUM>8049</REFNUM><AUTHORS><AUTHOR>Cechlarova,K.</AUTHOR><AUTHOR>Manlove,D.F.</AUTHOR></AUTHORS><YEAR>2005</YEAR><TITLE>The Exchange-Stable Marriage Problem</TITLE><PLACE_PUBLISHED>Discrete Applied Mathematics, volume 152</PLACE_PUBLISHED><PUBLISHER>Elsevier Science</PUBLISHER><PAGES>109-122</PAGES><ISBN>0166-218X</ISBN><LABEL>Cechlarova:2005:8049</LABEL><KEYWORDS><KEYWORD>Stable Marriage problem; Stable Roommates problem; Matching; Coalition-exchange-stable; Man-exchange-stable</KEYWORD></KEYWORDS<ABSTRACT>In this paper we consider instances of stable matching problems, namely the classical Stable Marriage (SM) and Stable Roommates (SR) problems and their variants. In such instances we consider a stability criterion that has recently been proposed, that of <i>exchange-stability</i>. In particular, we prove that ESM - the problem of deciding, given an SM instance, whether an exchange-stable matching exists - is NP-complete. This result is in marked constrast with Gale and Shapley's classical linear-time algorithm for finding a stable matching in an instance of SM. We also extend the result for ESM to the SR case. Finally, we study some variants of ESM under weaker forms of exchange-stability, presenting both polynomial-time solvability and NP-completeness results for the corresponding existence questions.</ABSTRACT><URL>http://dx.doi.org/10.1016/j.dam.2005.06.003</URL></RECORD></RECORDS></XML>