Understanding popular matchings via stable matchings

DOI10.1137/19M124770XzbMATH Open1483.91135arXiv1811.06897OpenAlexW4206620227MaRDI QIDQ5028352FDOQ5028352

Authors: Ágnes Cseh, Yuri Faenza, Telikepalli Kavitha, Vladlena Powers 

Publication date: 9 February 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Let $G=(AcupB,E)$ be an instance of the stable marriage problem with strict preference lists. A matching $M$ is popular in $G$ if $M$ does not lose a head-to-head election against any matching where vertices are voters. Every stable matching is a min-size popular matching; another subclass of popular matchings that always exist and can be easily computed is the set of dominant matchings. A popular matching $M$ is dominant if $M$ wins the head-to-head election against any larger matching. Thus every dominant matching is a max-size popular matching and it is known that the set of dominant matchings is the linear image of the set of stable matchings in an auxiliary graph. Results from the literature seem to suggest that stable and dominant matchings behave, from a complexity theory point of view, in a very similar manner within the class of popular matchings. The goal of this paper is to show that indeed there are differences in the tractability of stable and dominant matchings, and to investigate further their importance for popular matchings. First, we show that it is easy to check if all popular matchings are also stable, however it is co-NP hard to check if all popular matchings are also dominant. Second, we show how some new and recent hardness results on popular matching problems can be deduced from the NP-hardness of certain problems on stable matchings, also studied in this paper, thus showing that stable matchings can be employed not only to show positive results on popular matching (as is known), but also most negative ones. Problems for which we show new hardness results include finding a min-size (resp. max-size) popular matching that is not stable (resp. dominant). A known result for which we give a new and simple proof is the NP-hardness of finding a popular matching when $G$ is non-bipartite.

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

Recommendations

• Popular matchings and limits to tractability
• Popular edges and dominant matchings
• Popular edges and dominant matchings
• Popular matchings of desired size
• Popular matchings in the marriage and roommates problems

zbMATH Keywords

complexitystable matchingpopular matchingdominant matching

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Cites Work

• Title not available (Why is that?)
• College Admissions and the Stability of Marriage
• The geometry of fractional stable matchings and its applications
• Linear programming brings marital bliss
• Popular matchings in the marriage and roommates problems
• Characterization of stable matchings as extreme points of a polytope
• Popular Matchings
• An efficient algorithm for the “stable roommates” problem
• Popular Matchings and Limits to Tractability
• Network flow and 2-satisfiability
• Popular mixed matchings
• A new fixed point approach for stable networks and stable marriages
• A New Approach to Stable Matching Problems
• Popular matchings in the stable marriage problem
• Popular edges and dominant matchings
• A Size-Popularity Tradeoff in the Stable Marriage Problem
• Popular Matching in Roommates Setting Is NP-hard
• Popular Half-Integral Matchings.
• Quasi-popular Matchings, Optimality, and Extended Formulations
• Popular Matchings with Two-Sided Preferences and One-Sided Ties
• Popularity, Mixed Matchings, and Self-Duality

Cited In (8)

• Maintaining Near-Popular Matchings
• Quasi-Popular Matchings, Optimality, and Extended Formulations
• Popular Matchings: Structure and Strategic Issues
• Popularity, Mixed Matchings, and Self-Duality
• Popular Matchings -- structure and cheating strategies
• Popular critical matchings in the many-to-many setting
• Popular Matchings: Structure and Algorithms
• Maximum matchings and popularity

This page was built for publication: Understanding popular matchings via stable matchings

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