Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

DOI10.1016/J.IC.2022.104943MaRDI QIDQ2105427zbMATH OpenOpenAlexFDO

Authors Robert Bredereck, Klaus Heeger, Dušan Knop, Rolf Niedermeier

Publication date 8 December 2022

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

fixed-parameter tractabilitystable matchingW[1-hardness]tree-cut widthdisjoint path modulator

Mathematics Subject Classification ID

Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
• Parameterized algorithms for stable matching with ties and incomplete lists
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• How hard is it to satisfy (almost) all roommates?
• Parameterized complexity and local search approaches for the stable marriage problem with ties

Cites work

• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• A 3/2-Approximation Algorithm for General Stable Marriage
• A fine-grained view on stable many-to-one matching problems with lower and upper quotas
• A linear-time algorithm for testing the truth of certain quantified Boolean formulas
• A new fixed point approach for stable networks and stable marriages
• Algorithmic applications of tree-cut width
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An efficient algorithm for the “stable roommates” problem
• Balanced stable marriage: how close is close enough?
• Bribery and control in stable marriage
• College Admissions and the Stability of Marriage
• Hard variants of stable marriage.
• How hard is it to satisfy (almost) all roommates?
• Immersions in highly edge connected graphs
• Lean Tree-Cut Decompositions: Obstructions and Algorithms
• Multidimensional stable roommates with master list
• NP-complete stable matching problems
• New races in parameterized algorithmics
• On a generalization of the stable roommates problem
• On structural parameterizations of the bounded-degree vertex deletion problem
• On the complexity of \(k\)-SAT
• On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
• Pairwise kidney exchange
• Parameterized Complexity of Stable Roommates with Ties and Incomplete Lists Through the Lens of Graph Parameters
• Parameterized algorithms
• Parameterized algorithms for stable matching with ties and incomplete lists
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• SAT-encodings for treecut width and treedepth
• Solving hard stable matching problems involving groups of similar agents
• Stable assignment with couples: parameterized complexity and local search
• Stable matching with preferences derived from a psychological model
• Stable matchings with covering constraints: a complete computational trichotomy
• The stable marriage problem with ties and restricted edges
• The stable roommates problem with short lists
• The structure of graphs not admitting a fixed immersion
• The structure of stable marriage with indifference
• Tight lower bounds for certain parameterized NP-hard problems
• Treewidth. Computations and approximations

Cited in

(1)

• Effective data reduction for strongly stable matching in very sparse graphs

This page was built for publication: Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

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