Preference Swaps for the Stable Matching Problem

DOI10.1016/J.TCS.2022.11.003arXiv2112.15361MaRDI QIDQ6387166FDOQ6387166

Authors: Eduard Eiben, G. Gutin, Philip R. Neary, Clément Rambaud, Magnus Wahlström, A. Yeo 

Publication date: 31 December 2021

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 to find 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.

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Preference Swaps for the Stable Matching Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6387166)