Stable matchings with covering constraints: a complete computational trichotomy

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.

Subjects

Stable marriage

Lower quotas

Fixed-parameter algorithms

DDC Class

510: Mathematik

Funding(s)

Projekt DEAL

Lizenz

https://creativecommons.org/licenses/by/4.0/

Name

Mnich-Schlotter2020_Article_StableMatchingsWithCoveringCon.pdf

Size

954.56 KB

Format

Adobe PDF

Options

Stable matchings with covering constraints: a complete computational trichotomy