2020/02/07 by Mnich, Matthias, Schlotter, Ildikó
#Fixed-parameter algorithms #Lower quotas #Mathematik #Stable marriage
paper · doi:10.15480/882.2637
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.