The stable marriage problem with ties and restricted edges
- In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching.
Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum sizeIn the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching.
Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.…
| Author details: | Agnes CsehORCiD, Klaus Heeger |
|---|---|
| DOI: | https://doi.org/10.1016/j.disopt.2020.100571 |
| ISSN: | 1572-5286 |
| ISSN: | 1873-636X |
| Title of parent work (English): | Discrete optimization |
| Publisher: | Elsevier |
| Place of publishing: | Amsterdam |
| Publication type: | Article |
| Language: | English |
| Date of first publication: | 2020/03/04 |
| Publication year: | 2020 |
| Release date: | 2023/09/27 |
| Tag: | complexity; restricted edges; stable matchings |
| Volume: | 36 |
| Article number: | 100571 |
| Number of pages: | 11 |
| Funding institution: | Cooperation of Excellences, Hungary Grant [KEP-6/2019]; Hungarian; Academy of SciencesHungarian Academy of Sciences [LP2016-3/2019]; OTKAOrszagos Tudomanyos Kutatasi Alapprogramok (OTKA) [K128611]; DFG,; Germany Research Training Group 2434 "Facets of Complexity"German; Research Foundation (DFG); COST Action European Network for Game Theory; [CA16228]; Janos Bolyai Research Fellowship, HungaryHungarian Academy of; Sciences |
| Organizational units: | An-Institute / Hasso-Plattner-Institut für Digital Engineering gGmbH |
| DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
| Peer review: | Referiert |
| Publishing method: | Open Access / Hybrid Open-Access |
| License (German): |  CC-BY - Namensnennung 4.0 International |
