You are here

On the Complexity of Robust Stable Marriage

Publication Type: 
Refereed Conference Meeting Proceeding
Robust Stable Marriage 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. Formally, 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' others. In this paper, we focus on the complexity of finding an (a,b)-supermatch. In order to show finding an (a,b)-supermatch is NP-Complete we first introduce a SAT formulation that is \NPC~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. We also focus on studying the threshold between the cases in P and NP-Complete for this problem.
Conference Name: 
International Conference on Combinatorial Optimization and Applications, COCOA 2017
Digital Object Identifer (DOI): 
Publication Date: 
National University of Ireland, Cork (UCC)
Open access repository: 
Publication document: