Constrained Stable Marriage with Free Edges or Few Blocking Pairs

Abstract

Given two disjoint sets U and W, where the members (also called agents) of U and W are called men and women, respectively, and each agent is associated with an ordered preference list that ranks a subset of the agents from the opposite gender, a stable matching is a set of pairwise disjoint woman-man pairs admitting no blocking pairs. A blocking pair refers to a woman and a man, who prefer each other to their partners in the matching. Gale and Shapley proved that a stable matching exists for every instance. Since then, a lot of stable matching variants have been introduced. For instance, the $\pi$-stable marriage problem asks for a stable matching satisfying a given constraint $\pi$. Unlike in the unconstrained case, a given instance may not admit a $\pi$-stable matching and one has to accept a semi-stable matching satisfying $\pi$, for instance, a matching satisfying $\pi$ and admitting few blocking pairs. In this paper, we study two such problems, namely, $\pi$ -Stable Marriage with Free Edges ($\pi$-SMFE) and $\pi$ -Stable Marriage with $t$ -Blocking Pairs ($\pi$-SM$t$BP). $\pi$-SMFE seeks for a matching M satisfying $\pi$ and the condition that all blocking pairs occurring in M are from a given set F of woman-man pairs, while the solution matchings of $\pi$-SM$t$BP need to satisfy $\pi$ and admit at most t blocking pairs. We examine four constraints, Regret, Egalitarian, Forced, and Forbidden, and prove that both $\pi$-SMFE and $\pi$-SM$t$BP are NP-hard for all four constraints even with complete preference lists. Concerning parameterized complexity, we establish a series of fixed-parameter tractable and intractable results for $\pi$-SMFE and $\pi$-SM$t$BP with respect to some structural parameters such as the number of agents and the number of free edges/blocking pairs.

Supported by NSFC 61772314, 61761136017 and 62072275.