You are here

On the Complexity of Robust Stable Marriage

Authors: 
Publication Type: 
Refereed Original Article
Abstract: 
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.
Digital Object Identifer (DOI): 
NOT YET
Publication Status: 
In Press
Date Accepted for Publication: 
Saturday, 2 September, 2017
Publication Date: 
20/12/2017
Journal: 
International Conference on Combinatorial Optimization and Applications (COCOA)
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No