You are here

Complexity Study for the Robust Stable Marriage Problem

Authors: 

Begum Genc, Mohamed Siala, Gilles Simonin, Barry O'Sullivan

Publication Type: 
Refereed Original Article
Abstract: 
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.
Digital Object Identifer (DOI): 
10.1016/j.tcs.2018.12.017
Publication Status: 
Published
Date Accepted for Publication: 
Thursday, 20 December, 2018
Publication Date: 
02/01/2019
Journal: 
Theoretical Computer Science
Institution: 
National University of Ireland, Cork (UCC)
Open access repository: 
No