On the complexity of Robust Stable Marriage

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

On the complexity of Robust Stable Marriage

Files

4581.pdf(108.68 KB)

Accepted version

Date

2017-11-16

Authors

Genc, Begum

Siala, Mohamed

Simonin, Gilles

O'Sullivan, Barry

Publisher

Springer International Publishing

Published Version

10.1007/978-3-319-71147-8_30

Abstract

Robust Stable Marriage (RSM) 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. 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 also the partners of at most b other couples. In order to show deciding if there exists an (a, b)-supermatch is NPNP -complete, we first introduce a SAT formulation that is NPNP -complete 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.

Keywords

Robust Stable Marriage (RSM) , Stable Marriage problem , Combinatorial optimization , A-stable , Classical stable marriages , Dichotomy theorem , NP Complete , Stable marriages , Stable matching

Citation

Genc, B., Siala, M., Simonin, G. and O’Sullivan, B. (2017) 'On the Complexity of Robust Stable Marriage', in Gao, X., Du, H. & Han, M. (eds.) Combinatorial Optimization and Applications: 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part II, Lecture Notes in Computer Science, LCNS vol. 10335, Cham: Springer International Publishing, pp. 441-448. doi: 10.1007/978-3-319-71147-8_30