Preference Swaps for the Stable Matching Problem
share
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. To generalize this result to the many-to-many version of SMP, we introduce a new representation of SMP as an extended bipartite graph and reduce the problem to submodular minimization. It is a natural problem to establish 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 it is NP-hard to decide whether at most k swaps are enough to turn I into an instance with a stable perfect matching. Moreover, this problem parameterized 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.
READ FULL TEXT