Stable marriage with covering constraints -- a complete computational trichotomy

DOI10.1007/978-3-319-66700-3_25MaRDI QIDQ681890zbMATH OpenOpenAlexFDO

Authors Matthias Mnich, Ildikó Schlotter

Publication date 13 February 2018

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

zbMATH Keywords

matchingstable marriagecomplete complexity trichotomycovering constraints

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Abstract: We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy that, for each choice of the studied parameters, classifies SMC as polynomial-time solvable, NP-hard and fixed-parameter tractable, or NP-hard and W[1]-hard. We also classify all cases of one-sided constraints where only women may be distinguished.

Recommendations

• Stable matchings with covering constraints: a complete computational trichotomy
• scientific article; zbMATH DE number 45086
• scientific article; zbMATH DE number 2084708
• A formal theory for the complexity class associated with the stable marriage problem
• Lower Bounds for the Stable Marriage Problem and Its Variants
• Approximability results for stable marriage problems with ties.
• Hardness and approximation results for some variants of stable marriage problem
• Better and simpler approximation algorithms for the stable marriage problem
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• A tight approximation bound for the stable marriage problem with restricted ties

Cited in

(13)

• Envy-free matchings with lower quotas
• Solving hard stable matching problems involving groups of similar agents
• How long does it take for all users in a social network to choose their communities?
• How hard is it to satisfy (almost) all roommates?
• Stable matchings with covering constraints: a complete computational trichotomy
• Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
• scientific article; zbMATH DE number 7278072 (Why is no real title available?)
• Constrained stable marriage with free edges or few blocking pairs
• A formal theory for the complexity class associated with the stable marriage problem
• Non-existence of stable social groups in information-driven networks
• How long does it take for all users in a social network to choose their communities?
• Balanced stable marriage: how close is close enough?
• Stable marriage with groups of similar agents

This page was built for publication: Stable marriage with covering constraints -- a complete computational trichotomy

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