Stable matchings with covering constraints: a complete computational trichotomy

Mnich, Matthias; Schlotter, Ildikó

doi:10.1007/s00453-019-00636-y

Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2637

Publisher DOI:	10.1007/s00453-019-00636-y
Title:	Stable matchings with covering constraints: a complete computational trichotomy
Language:	English
Authors:	Mnich, Matthias Schlotter, Ildikó
Keywords:	Stable marriage;Lower quotas;Fixed-parameter algorithms
Issue Date:	6-Feb-2020
Publisher:	Springer
Source:	Algorithmica (2020)
Journal or Series Name:	Algorithmica
Abstract (english):	Stable matching problems with lower quotas are fundamental in academic hiring andensuring operability of rural hospitals. Only few tractable (polynomial-time solvable)cases of stable matching with lower quotas have been identified; most such problemsareNP-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440–465, 2016). We therefore consider stable matching problems with lower quotas under arelaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitalswe focus on the case when all hospitals have upper quota equal to 1, which general-izes the setting of “arranged marriages” first considered by Knuth (Mariages stableset leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Universitéde Montréal, Montreal, 1976). We investigate how a set of natural parameters, namelythe maximum length of preference lists for men and women, the number of distin-guished men and women, and the number of blocking pairs allowed determine thecomputational tractability of this problem. Our main result is a complete complexitytrichotomy: for each choice of parameters we either provide a polynomial-time algo-rithm, or anNP-hardness proof and fixed-parameter algorithm, orNP-hardness proofandW[1]-hardness proof. As corollary, we negatively answer a question by Hamadaet al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractabil-ity parameterized by optimal solution size. We also classify all cases of one-sidedconstraints where only women may be distinguished.
URI:	http://hdl.handle.net/11420/4786
DOI:	10.15480/882.2637
ISSN:	1432-0541
Institute:	Algorithmen und Komplexität E-11
Type:	(wissenschaftlicher) Artikel
Appears in Collections:	Publications with fulltext