Irving, R. W. and Manlove, D. F. (2002) The stable roommates problem with ties. Journal of Algorithms 43(1):85-105. http://eprints.gla.ac.uk/archive/00000011 Glasgow ePrints Service http://eprints.gla.ac.uk The Stable Roommates Problem with Ties∗
Robert W. Irving and David F. Manlove
Department of Computing Science, University of Glasgow, Glasgow G12 8QQ, UK.
Email: {rwi,davidm}@dcs.gla.ac.uk.

Abstract
We study the variant of the well-known Stable Roommates problem in which participants are permitted to express ties in their preference lists. In this setting, more than one definition of stability is possible. Here we consider two of these stability criteria, so-called super-stability and weak stability. We present a linear-time algorithm for finding a super-stable matching if one exists, given a Stable Roommates instance with ties. This contrasts with the known NP-hardness of the analogous problem under weak stability. We also extend our algorithm to cope with preference lists that are incomplete and/or partially ordered. On the other hand, for a given Stable Roommates instance with ties and incomplete lists, we show that the weakly stable matchings may be of different sizes, and the problem of finding a maximum cardinality weakly stable matching is NP-hard, though approximable within a factor of 2.
Keywords: stable matching problem; indifference; super-stability; weak stability; linear-time algorithm; NP-completeness; approximation algorithm

1

Introduction

In a given instance of the Stable Roommates problem (SR), each of 2n participants ranks the others in strict order of preference. A matching is a set of n disjoint (unordered) pairs of participants. A matching M in an instance of SR is stable if there are no two participants x and y, each of whom prefers the other to his partner in M . Such a pair is said to block M , or to be a blocking pair with respect to M . Gale and Shapley [2] were the first to study
SR, and gave an example instance which does not admit a stable matching. Irving [7] solved a problem posed by Knuth [12] when he described an O(n2 ) algorithm (henceforth
Algorithm SR) – linear in the input size – to find a stable matching if one exists, for a given instance of SR. Subsequently, Gusfield [4] and Irving [8] explored structural aspects of SR, and a comprehensive discussion of the problem is given by Gusfield and Irving [5].
In addition, Tan [18] introduced the concept of a stable partition in an instance I of SR, which provides a ‘succinct certificate’ in the case that I does not admit a stable matching.
More recently, Feder et al. [1] presented an O(n log 3 n) parallel algorithm for finding a stable matching if one exists, for a given instance of SR.
Note that SR is a non-bipartite extension of the classical Stable Marriage problem
(SM) [5]. In an instance of SM, the set of participants is partitioned into two disjoint sets, the men and women, and each person ranks all members of the opposite sex in strict order of preference. An analogous stability definition holds in this context. It is known that every instance of SM admits at least one stable matching, and such a matching may be found in linear time using the Gale/Shapley algorithm [2].
∗

This work was supported by Engineering and Physical Sciences Research Council grant number
GR/M13329.

1

1.1

Incomplete preference lists

SR may be generalised by allowing the preference lists of those involved to be incomplete
(we refer to this problem as SRI). In this case, we say that participant p is acceptable to participant q if p appears on the preference list of q, and unacceptable otherwise. A matching M in an instance of SRI must satisfy the property that {x, y} ∈ M implies that x, y find each other acceptable. The revised notion of stability may be defined as follows: given an instance of SRI, a matching M is stable if there are no two participants x and y, each of whom either is