The Constant Inapproximability of the Parameterized Dominating Set Problem
From MaRDI portal
Publication:4634028
DOI10.1137/17M1127211zbMath1422.68082arXiv1511.00075MaRDI QIDQ4634028
Publication date: 7 May 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1511.00075
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Time-approximation trade-offs for inapproximable problems ⋮ Approximation and hardness of shift-Bribery ⋮ Parameterized Approximation Schemes for Independent Set of Rectangles and Geometric Knapsack ⋮ Parameterized Approximation Algorithms for Bidirected Steiner Network Problems
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- Parameterized approximation of dominating set problems
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- Two combinatorial covering theorems
- On the existence of subexponential parameterized algorithms
- On a Vizing-like conjecture for direct product graphs
- Completely inapproximable monotone and antimonotone parameterized problems
- On subexponential and FPT-time inapproximability
- Fixed-parameter approximation: conceptual framework and approximability results
- Parametrized complexity theory.
- Fixed-Parameter and Approximation Algorithms: A New Look
- Algorithmic construction of sets for k -restrictions
- Proof verification and the hardness of approximation problems
- A threshold of ln n for approximating set cover
- The Projection Games Conjecture and the NP-Hardness of ln n-Approximating Set-Cover
- Parameterized Approximation Problems
- Linear FPT reductions and computational lower bounds
- Probabilistic checking of proofs
- A Greedy Heuristic for the Set-Covering Problem
- On the hardness of approximating minimization problems
- Color-coding
- A Tight Analysis of the Greedy Algorithm for Set Cover
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Reducibility among Combinatorial Problems
- On the parameterized complexity of approximating dominating set
- Analytical approach to parallel repetition
- The Parameterized Complexity of k-B<scp>iclique</scp>
- Parameterized Algorithms
- On the complexity of \(k\)-SAT
