Characterisation of strongly stable matchings

DOI10.1137/1.9781611974331.CH8MaRDI QIDQ4575583zbMATH OpenOpenAlexFDO

Authors Adam Kunysz, Katarzyna Paluch, Pratik Ghosal

Publication date 16 July 2018

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

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

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)

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.

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

Cited in

(16)

• Strongly stable and maximum weakly stable noncrossing matchings
• Characterization of super-stable matchings
• Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings
• Strongly stable and maximum weakly stable noncrossing matchings
• The strongly stable roommates problem
• Pairwise Preferences in the Stable Marriage Problem
• A characterization of strongly stable fractional matchings
• Core and stability notions in many-to-one matching markets with indifferences
• scientific article; zbMATH DE number 7561396 (Why is no real title available?)
• On the stable \(b\)-matching problem in multigraphs
• Adapting stable matchings to forced and forbidden pairs
• STACS 2004
• Stable matchings in trees
• Strongly stable assignment
• 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)