Mnich, MatthiasMatthiasMnichSchlotter, IldikóIldikóSchlotter2020-02-072020-02-072020-02-06Algorithmica (2020)http://hdl.handle.net/11420/4786Stable 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.en1432-05412020Springerhttps://creativecommons.org/licenses/by/4.0/Stable marriageLower quotasFixed-parameter algorithmsMathematikJournal Articleurn:nbn:de:gbv:830-882.07183910.15480/882.263710.1007/s00453-019-00636-y10.15480/882.2637Journal Article