Preference swaps for the stable matching problem

Eduard Eiben, Gregory Gutin*, Philip R. Neary, Clément Rambaud, Magnus Wahlström, Anders Yeo

*Kontaktforfatter

Publikation: Bidrag til tidsskriftTidsskriftartikelForskningpeer review

42 Downloads (Pure)

Abstract

An instance I of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in I is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of I. Boehmer et al. (2021) designed a polynomial-time algorithm for finding the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most k swaps are enough to turn I into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by k is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.

OriginalsprogEngelsk
TidsskriftTheoretical Computer Science
Vol/bind940
Sider (fra-til)222-230
ISSN0304-3975
DOI
StatusUdgivet - 9. jan. 2023

Bibliografisk note

Funding Information:
We are grateful to the referee for a number of helpful suggestions.

Publisher Copyright:
© 2022 The Author(s)

Fingeraftryk

Dyk ned i forskningsemnerne om 'Preference swaps for the stable matching problem'. Sammen danner de et unikt fingeraftryk.

Citationsformater