UNIVERSITY of GLASGOW

Computing at Glasgow University
 
Paper ID: 8049

The Exchange-Stable Marriage Problem
Cechlarova,K. Manlove,D.F.

Publication Type: Journal
Appeared in: Discrete Applied Mathematics, volume 152
Page Numbers : 109-122
Publisher: Elsevier Science
Year: 2005
ISBN/ISSN: 0166-218X

URL: This publication is available at this URL.

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 exchange-stability. 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.

Keywords: Stable Marriage problem; Stable Roommates problem; Matching; Coalition-exchange-stable; Man-exchange-stable


PDF Bibtex entry Endnote XML