Paper ID: 8553
Efficient algorithms for generalised stable marriage and roommates problems
Theoretical Computer Science Volume 381
Page Numbers : 162-176
Publisher: Elsevier Science
URL: This publication is available at this URL.
We consider a generalisation of the Stable Roommates problem (SR), in which preference lists may be partially ordered and forbidden pairs may be present, denoted
by SRPF. This includes, as a special case, a corresponding generalisation of the classical Stable Marriage problem (SM), denoted by SMPF. By extending previous work of
Feder, we give a two-step reduction from SRPF to 2-SAT. This has many consequences, including fast algorithms for a range of problems associated with finding "optimal"
stable matchings and listing all solutions, given variants of SR and SM. For example, given an SMPF instance I, we show that there exists an O(m) "succinct" certificate
for the unsolvability of I, an O(m) algorithm for finding all the super-stable pairs in I, an O(m+kn) algorithm for listing all the superstable matchings in I, an O(m1.5) algorithm for finding an egalitarian superstable matching in I, and an O(m) algorithm
for finding a minimum regret super-stable matching in I, where n is the number of men, m is the total length of the preference lists, and k is the number of super-stable
matchings in I . Analogous results apply in the case of SRPF.
Keywords: Stable Roommates problem; Stable marriage problem; Partial order; Forbidden pair; Super-stable matching