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 metadatas

Cited literature [27 references]  Display  Hide  Download

https://hal.laas.fr/hal-01974431
Contributor : Mohamed Siala <>
Submitted on : Tuesday, January 8, 2019 - 6:27:32 PM
Last modification on : Saturday, October 26, 2019 - 1:36:30 AM

File

19-TCS.pdf
Files produced by the author(s)

Identifiers

Citation

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

Share

Metrics

Record views

374

Files downloads

189