Dec. 11, 2018, 10:15 a.m.

Title: An Algorithm for the Maximum Weight Strongly Stable Matching Problem

Speaker: Adam Kunysz

Time and place: Tuesday, 11th of December 2018, 10:15 am, room 310.


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].

Accepted to ISAAC 2018.