Characterisation of strongly stable matchings

DOI10.1137/1.9781611974331.CH8zbMATH Open1410.05166arXiv1506.00677OpenAlexW2952834091MaRDI QIDQ4575583FDOQ4575583

Katarzyna Paluch, Pratik Ghosal, Adam Kunysz

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: An instance of a strongly stable matching problem (SSMP) is an undirected bipartite graph $G=(AcupB,E)$, with an adjacency list of each vertex being a linearly ordered list of ties, which are subsets of vertices equally good for a given vertex. Ties are disjoint and may contain one vertex. A matching $M$ is a set of vertex-disjoint edges. An edge $(x,y)inEsetminusM$ is a {em 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 {em strongly stable} if there is no blocking edge with respect to it. We present an algorithm for the generation of all strongly stable matchings, thus solving an open problem already stated in the book by Gusfield and Irving cite{GI}. It has previously been shown that strongly stable matchings form a distributive lattice and although the number of strongly stable matchings can be exponential in the number of vertices, we show that there exists a partial order with $O(m)$ elements representing all strongly stable matchings, where $m$ denotes the number of edges in the graph. We give two algorithms that construct two such representations: one in $O(n{m}^2)$ time and the other in $O(nm)$ time, where $n$ denotes the number of vertices in the graph. Note that the construction of the second representation has the same time complexity as that of computing a single strongly stable matching.

Full work available at URL: https://arxiv.org/abs/1506.00677

Recommendations

• The strongly stable roommates problem
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• STACS 2004
• Strongly stable assignment
• A characterization of strongly stable fractional matchings

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (8)

• Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings
• Characterization of super-stable matchings
• Pairwise Preferences in the Stable Marriage Problem
• Core and stability notions in many-to-one matching markets with indifferences
• Title not available (Why is that?)
• Adapting stable matchings to forced and forbidden pairs
• Dynamic rank-maximal and popular matchings
• Marriage market with indifferences: a linear programming approach

This page was built for publication: Characterisation of strongly stable matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575583)