Complexity Study for the Robust Stable Marriage Problem

The Robust Stable Marriage problem (RSM)is a variant of the classic Stable Marriage problem in which the robustness of a given stable matching is measured by the number of modifications required to find an alternative stable matching should some pairings break due to an unforeseen event. We focus on the complexity of finding an (a,b)-supermatch. An (a,b)-supermatch is defined as a stable matching in which if any a (non-fixed)men/women break up it is possible to find another stable matching by changing the partners of those a men/women and the partners of at most b others. We first discuss a model based on independent sets for finding (1,1)-supermatches. Secondly, in order to show that deciding whether or not there exists a (1,b)-supermatch is NP-complete, we first introduce a SAT formulation for which the decision problem is NP-complete by using Schaefer's Dichotomy Theorem. We then show the equivalence between this SAT formulation and finding a (1,1)-supermatch on a specific family of instances. We also focus on studying the threshold between the cases in P and NP-complete for this problem.