Title: On the Complexity of Robust Stable Marriage,
Abstract: Robust Stable Marriage (RSM) is a variant of the classical Stable Marriage
problem, where the robustness of a given stable matching is measured by the
number of modifications required for repairing it in case an unforeseen event
occurs. 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 also the partners of at
most 'b' other couples. In order to show deciding if there exists an
(a,b)-supermatch is NP-Complete, we first introduce a SAT formulation that is
NP-Complete by using Schaefer's Dichotomy Theorem. Then, we show the
equivalence between the SAT formulation and finding a (1,1)-supermatch on a
specific family of instances.