Computing at Glasgow University
Paper ID: 8909

Stable Marriage with Ties and Bounded Length Preference Lists
Irving,R.W. Manlove,D.F. O'Malley,G.

Publication Type: Journal
Appeared in: Journal of Discrete Algorithms, volume 7
Page Numbers : 213-219
Publisher: Elsevier Science
Year: 2009
ISBN/ISSN: 1570-8667

URL: This publication is available at this URL.


We consider variants of the classical stable marriage problem in which preference lists may contain ties, and may be of bounded length. Such restrictions arise naturally in practical applications, such as centralised matching schemes that assign graduating medical students to their first hospital posts. In such a setting, weak stability is the most common solution concept, and it is known that weakly stable matchings can have different sizes. This motivates the problem of finding a maximum cardinality weakly stable matching, which is known to be NP-hard in general. We show that this problem is solvable in polynomial time if each man's list is of length at most 2 (even for women's lists that are of unbounded length). However if each man's list is of length at most 3, we show that the problem becomes NP- hard (even if each women's list is of length at most 3) and not approximable within some delta>1 (even if each woman's list is of length at most 4).

Keywords: Stable marriage problem; ties; incomplete lists; NP-hardness; polynomial-time algorithm

PDF Bibtex entry Endnote XML