Chen, Jiehua ;
Hermelin, Danny ;
Sorge, Manuel ;
Yedidsion, Harel
How Hard Is It to Satisfy (Almost) All Roommates?
Abstract
The classic Stable Roommates problem (the nonbipartite generalization of the wellknown Stable Marriage problem) asks whether there is a stable matching for a given set of agents, i.e. a partitioning of the agents into disjoint pairs such that no two agents induce a blocking pair. Herein, each agent has a preference list denoting who it prefers to have as a partner, and two agents are blocking if they prefer to be with each other rather than with their assigned partners.
Since stable matchings may not be unique, we study an NPhard optimization variant of Stable Roommates, called Egal Stable Roommates, which seeks to find a stable matching with a minimum egalitarian cost gamma, i.e. the sum of the dissatisfaction of the agents is minimum. The dissatisfaction of an agent is the number of agents that this agent prefers over its partner if it is matched; otherwise it is the length of its preference list. We also study almost stable matchings, called MinBlockPair Stable Roommates, which seeks to find a matching with a minimum number beta of blocking pairs. Our main result is that Egal Stable Roommates parameterized by gamma is fixedparameter tractable, while MinBlockPair Stable Roommates parameterized by beta is W[1]hard, even if the length of each preference list is at most five.
BibTeX  Entry
@InProceedings{chen_et_al:LIPIcs:2018:9039,
author = {Jiehua Chen and Danny Hermelin and Manuel Sorge and Harel Yedidsion},
title = {{How Hard Is It to Satisfy (Almost) All Roommatesl}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {35:135:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9039},
URN = {urn:nbn:de:0030drops90398},
doi = {10.4230/LIPIcs.ICALP.2018.35},
annote = {Keywords: NPhard problems Data reduction rules Kernelizations Parameterized complexity analysis and algorithmics}
}
2018
Keywords: 

NPhard problems Data reduction rules Kernelizations Parameterized complexity analysis and algorithmics 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 