Popular matchings and limits to tractability
From MaRDI portal
(Redirected from Publication:5236364)
Abstract: We consider popular matching problems in both bipartite and non-bipartite graphs with strict preference lists. It is known that every stable matching is a min-size popular matching. A subclass of max-size popular matchings called dominant matchings has been well-studied in bipartite graphs: they always exist and there is a simple linear time algorithm to find one. We show that stable and dominant matchings are the only two tractable subclasses of popular matchings in bipartite graphs; more precisely, we show that it is NP-complete to decide if admits a popular matching that is neither stable nor dominant. We also show a number of related hardness results, such as (tight) inapproximability of the maximum weight popular matching problem. In non-bipartite graphs, we show a strong negative result: it is NP-hard to decide whether a popular matching exists or not, and the same result holds if we replace popular with dominant. On the positive side, we show the following results in any graph: - we identify a subclass of dominant matchings called strongly dominant matchings and show a linear time algorithm to decide if a strongly dominant matching exists or not; - we show an efficient algorithm to compute a popular matching of minimum cost in a graph with edge costs and bounded treewidth.
Recommendations
Cited in
(40)- Unpopularity factor in the marriage and roommates problems
- Popular branchings and their dual certificates
- Two problems in max-size popular matchings
- Popular matchings in complete graphs
- Finding popular branchings in vertex-weighted directed graphs
- Popular Matchings -- structure and cheating strategies
- From heaps of matches to the limits of computability
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Popular Half-Integral Matchings.
- Popular and Clan-Popular b-Matchings
- Popularity, Mixed Matchings, and Self-Duality
- Understanding popular matchings via stable matchings
- Popular branchings and their dual certificates
- Quasi-popular matchings, optimality, and extended formulations
- Popular Matchings in Complete Graphs
- Finding and Recognizing Popular Coalition Structures
- Quasi-popular Matchings, Optimality, and Extended Formulations
- Popular Matchings: Structure and Algorithms
- Finding strongly popular \(b\)-matchings in bipartite graphs
- On weakly and strongly popular rankings
- Maximum matchings and popularity
- Popular matchings with weighted voters
- Computational complexity of \(k\)-stable matchings
- Stable matchings, one-sided ties, and approximate popularity
- Solving the maximum popular matching problem with matroid constraints
- Popularity on the roommate diversity problem
- Popularity on the roommate diversity problem
- Max-utility matchings with popularity via critical vertices
- Min-cost popular matchings
- Popular matchings with one-sided bias
- The popular matching problem in the roommates instance remains NP-hard in bounded degree graphs
- Perfect matchings and popularity in the many-to-many setting
- Matchings, relaxed popularity, and optimality
- Popular solutions for optimal matchings
- Popularity on the 3D-Euclidean stable roommates
- Testing popularity in linear time via maximum matching
- Popular roommates in simply exponential time
- Von Neumann-Morgenstern stability and internal closedness in matching theory
- Von Neumann-Morgenstern stability and internal closedness in matching theory
- Maximum matchings and popularity
This page was built for publication: Popular matchings and limits to tractability
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236364)
