Skip to Main content Skip to Navigation
New interface
Journal articles

Complexity Study for the Robust Stable Marriage Problem

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 N P-complete, we first introduce a SAT formulation for which the decision problem is N P-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.
Complete list of metadata

Cited literature [27 references]  Display  Hide  Download
Contributor : Mohamed Siala Connect in order to contact the contributor
Submitted on : Tuesday, January 8, 2019 - 6:27:32 PM
Last modification on : Thursday, November 17, 2022 - 4:48:10 PM


Files produced by the author(s)



Begum Genc, Mohamed Siala, Gilles Simonin, Barry O'Sullivan. Complexity Study for the Robust Stable Marriage Problem. Theoretical Computer Science, 2019, 775, pp.76-92. ⟨10.1016/j.tcs.2018.12.017⟩. ⟨hal-01974431⟩



Record views


Files downloads