License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2022.21
URN: urn:nbn:de:0030-drops-168194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16819/
Go to the corresponding LIPIcs Volume Portal

Boehmer, Niclas ; Heeger, Klaus ; Niedermeier, Rolf

Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems

pdf-format:
LIPIcs-MFCS-2022-21.pdf (0.8 MB)

Abstract

When computing stable matchings, it is usually assumed that the preferences of the agents in the matching market are fixed. However, in many realistic scenarios, preferences change over time. Consequently, an initially stable matching may become unstable. Then, a natural goal is to find a matching which is stable with respect to the modified preferences and as close as possible to the initial one. For Stable Marriage/Roommates, this problem was formally defined as Incremental Stable Marriage/Roommates by Bredereck et al. [AAAI '20]. As they showed that Incremental Stable Roommates and Incremental Stable Marriage with Ties are NP-hard, we focus on the parameterized complexity of these problems. We answer two open questions of Bredereck et al. [AAAI '20]: We show that Incremental Stable Roommates is W[1]-hard parameterized by the number of changes in the preferences, yet admits an intricate XP-algorithm, and we show that Incremental Stable Marriage with Ties is W[1]-hard parameterized by the number of ties. Furthermore, we analyze the influence of the degree of "similarity" between the agents' preference lists, identifying several polynomial-time solvable and fixed-parameter tractable cases, but also proving that Incremental Stable Roommates and Incremental Stable Marriage with Ties parameterized by the number of different preference lists are W[1]-hard.

BibTeX - Entry

@InProceedings{boehmer_et_al:LIPIcs.MFCS.2022.21,
  author =	{Boehmer, Niclas and Heeger, Klaus and Niedermeier, Rolf},
  title =	{{Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems}},
  booktitle =	{47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)},
  pages =	{21:1--21:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-256-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{241},
  editor =	{Szeider, Stefan and Ganian, Robert and Silva, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16819},
  URN =		{urn:nbn:de:0030-drops-168194},
  doi =		{10.4230/LIPIcs.MFCS.2022.21},
  annote =	{Keywords: Stable Marriage, Stable Roommates, adapting to changing preferences, NP-hardness, W\lbrack1\rbrack-hardness, XP, FPT, master lists, incremental algorithms}
}

Keywords: Stable Marriage, Stable Roommates, adapting to changing preferences, NP-hardness, W[1]-hardness, XP, FPT, master lists, incremental algorithms
Collection: 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Issue Date: 2022
Date of publication: 22.08.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI