On the parameterized complexity of approximating dominating set

DOI10.1145/3188745.3188896zbMath1429.68084arXiv1711.11029OpenAlexW2963957639MaRDI QIDQ5230381

Pasin Manurangsi, C. S. Karthik, Bundit Laekhanukit

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

dominating setset coverparameterized inapproximability

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25) Parameterized complexity, tractability and kernelization (68Q27) Communication complexity, information complexity (68Q11)

Related Items (11)

On the parameterized complexity of compact set packing ⋮ From Gap-Exponential Time Hypothesis to Fixed Parameter Tractable Inapproximability: Clique, Dominating Set, and More ⋮ On closest pair in Euclidean metric: monochromatic is as hard as bichromatic ⋮ The Constant Inapproximability of the Parameterized Dominating Set Problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Constant-Factor FPT Approximation for Capacitated k-Median ⋮ On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic ⋮ A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

This page was built for publication: On the parameterized complexity of approximating dominating set