Options
Stable marriage with covering constraints – a complete computational trichotomy
Publikationstyp
Conference Paper
Date Issued
2017
Sprache
English
Author(s)
TORE-URI
First published in
Number in series
10504 LNCS
Start Page
320
End Page
332
Citation
10th International Symposium on Algorithmic Game Theory (SAGT 2017)
Publisher DOI
ArXiv ID
Publisher
Springer
We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy that, for each choice of the studied parameters, classifies SMC as polynomial-time solvable, NP-hard and fixed-parameter tractable, or NP-hard and W[1]-hard. We also classify all cases of one-sided constraints where only women may be distinguished.
DDC Class
004: Informatik