Abstract
An instance of the maximum weight strongly stable matching problem with incomplete lists and ties is an undirected bipartite graph G = (A cup B, E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. We are also given a weight function w on the set E. An edge (x, y) in E setminus M is a blocking edge for M if by getting matched to each other neither of the vertices x and y would become worse off and at least one of them would become better off. A matching is strongly stable if there is no blocking edge with respect to it. The goal is to compute a strongly stable matching of maximum weight with respect to w.
We give a polyhedral characterisation of the problem and prove that the strongly stable matching polytope is integral. This result implies that the maximum weight strongly stable matching problem can be solved in polynomial time. Thereby answering an open question by Gusfield and Irving [Dan Gusfield and Robert W. Irving, 1989]. The main result of this paper is an efficient O(nm log{(Wn)}) time algorithm for computing a maximum weight strongly stable matching, where we denote n = V, m = E and W is a maximum weight of an edge in G. For small edge weights we show that the problem can be solved in O(nm) time. Note that the fastest known algorithm for the unweighted version of the problem has O(nm) runtime [Telikepalli Kavitha et al., 2007]. Our algorithm is based on the rotation structure which was constructed for strongly stable matchings in [Adam Kunysz et al., 2016].
BibTeX  Entry
@InProceedings{kunysz:LIPIcs:2018:9990,
author = {Adam Kunysz},
title = {{An Algorithm for the Maximum Weight Strongly Stable Matching Problem}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {42:142:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770941},
ISSN = {18688969},
year = {2018},
volume = {123},
editor = {WenLian Hsu and DerTsai Lee and ChungShou Liao},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9990},
URN = {urn:nbn:de:0030drops99902},
doi = {10.4230/LIPIcs.ISAAC.2018.42},
annote = {Keywords: Stable marriage, Strongly stable matching, Weighted matching, Rotation}
}
Keywords: 

Stable marriage, Strongly stable matching, Weighted matching, Rotation 
Seminar: 

29th International Symposium on Algorithms and Computation (ISAAC 2018) 
Issue Date: 

2018 
Date of publication: 

27.11.2018 