Kunysz, Adam
The Strongly Stable Roommates Problem
Abstract
An instance of the strongly stable roommates problem with incomplete lists and ties (SRTI) is an undirected nonbipartite graph G = (V,E), with an adjacency list being a linearly ordered list of ties, which are vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching M is a set of vertexdisjoint edges. An edge {x, y} in E\M is a blocking edge for M if x is either unmatched or strictly prefers y to its current partner in M, and y is either unmatched or strictly prefers x to its current partner in M or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We present an O(nm) time algorithm for computing a strongly stable matching, where we denote n = V and m = E. The best previously known solution had running time O(m^2) [Scott, 2005]. We also give a characterisation of the set of all strongly stable matchings. We show that there exists a partial order with O(m) elements representing the set of all strongly stable matchings, and we give an O(nm) algorithm for constructing such a representation. Our algorithms are based on a simple reduction to the bipartite version of the problem.
BibTeX  Entry
@InProceedings{kunysz:LIPIcs:2016:6401,
author = {Adam Kunysz},
title = {{The Strongly Stable Roommates Problem}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {60:160:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6401},
URN = {urn:nbn:de:0030drops64012},
doi = {10.4230/LIPIcs.ESA.2016.60},
annote = {Keywords: strongly stable matching, stable roommates, rotations, matching theory}
}
2016
Keywords: 

strongly stable matching, stable roommates, rotations, matching theory 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 