Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem

Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch

Abstract

An instance of the stable marriage problem is an undirected bipartite graph G = (X ∪ W, E) with linearly ordered adjacency lists with ties allowed in the ordering. A matching M is a set of edges, no two of which share an endpoint. An edge e = (a, b) ∈ E∖ M is a blocking edge for M if a is either unmatched or strictly prefers b to its partner in M, and b is unmatched, strictly prefers a to its partner in M, or is indifferent between them. A matching is strongly stable if there is no blocking edge with respect to it. We give an O(nm) algorithm for computing strongly stable matchings, where n is the number of vertices and m the number of edges. The previous best algorithm had running time O(m2). We also study this problem in the hospitals-residents setting, which is a many-to-one extension of the aforementioned problem. We give an O(m ∑h∈Hph) algorithm for computing a strongly stable matching in the hospitals-residents problem, where ph is the quota of a hospital h. The previous best algorithm had running time O(m2).
BibTeX
@inproceedings{kavitha2004strongly,
  author = {Telikepalli Kavitha and Kurt Mehlhorn and Dimitrios Michail and Katarzyna E. Paluch},
  title = {{Strongly stable matchings in time O(nm) and extension to the hospitals-residents problem}},
  booktitle = {STACS},
  year = {2004},
  doi = {10.1007/978-3-540-24749-4\_20},
}

Loading related content...

Figure