On the Complexity of Robust Stable Marriage
Publication Type:
Refereed Conference Meeting Proceeding
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.
Conference Name:
International Conference on Combinatorial Optimization and Applications, COCOA 2017
Digital Object Identifer (DOI):
10.1007/978-3-319-71147-8_30
Publication Date:
20/12/2017
Research Group:
Institution:
National University of Ireland, Cork (UCC)
Open access repository:
No
Publication document:
