Stable marriage with covering constraints – a complete computational trichotomy

Publikationstyp
Conference Paper
Date Issued
2017
Sprache
English
Author(s)
Mnich, Matthias  
Schlotter, Ildikó  
TORE-URI
http://hdl.handle.net/11420/4609
First published in
Lecture notes in computer science  
Number in series
10504 LNCS
Start Page
320
End Page
332
Citation
10th International Symposium on Algorithmic Game Theory (SAGT 2017)
Publisher DOI
10.1007/978-3-319-66700-3_25
ArXiv ID
1602.08230
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