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

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

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

(21)

• A characterization of graphs that ensure the existence of stable matchings
• Strongly stable and maximum weakly stable noncrossing matchings
• A faster algorithm for the Strongly Stable b-Matching Problem
• A characterization of strongly stable fractional matchings
• Stable matchings in trees
• Dynamic rank-maximal and popular matchings
• On the stable \(b\)-matching problem in multigraphs
• Marriage market with indifferences: a linear programming approach
• Strongly stable matchings in time \(O(nm)\) and extension to the hospitals-residents problem
• Strongly stable assignment
• The strongly stable roommates problem
• Strongly stable and maximum weakly stable noncrossing matchings
• Pairwise Preferences in the Stable Marriage Problem
• An algorithm for the maximum weight strongly stable matching problem
• Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings
• STACS 2004
• Core and stability notions in many-to-one matching markets with indifferences
• Adapting stable matchings to forced and forbidden pairs
• Strongly stable matchings under matroid constraints
• The strongly stable matching problem with closures
• Characterization of super-stable matchings

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)