On the parameterized complexity of approximating dominating set

DOI10.1145/3188745.3188896MaRDI QIDQ5230381zbMATH OpenOpenAlexFDO

Authors C. S. Karthik, B. Laekhanukit, Pasin Manurangsi

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 setparameterized inapproximabilityset cover

Mathematics Subject Classification ID

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

Abstract: We study the parameterized complexity of approximating the $k$-Dominating Set (DomSet) problem where an integer $k$ and a graph $G$ on $n$ vertices are given as input, and the goal is to find a dominating set of size at most $F(k)cdotk$ whenever the graph $G$ has a dominating set of size $k$. When such an algorithm runs in time $T(k)cdotpoly(n)$ (i.e., FPT-time) for some computable function $T$, it is said to be an $F(k)$-FPT-approximation algorithm for $k$-DomSet. We prove the following for every computable functions $T,F$ and every constant $varepsilon>0$: $$ Assuming $W[1]eqFPT$, there is no $F(k)$-FPT-approximation algorithm for $k$-DomSet. $$ Assuming the Exponential Time Hypothesis (ETH), there is no $F(k)$-approximation algorithm for $k$-DomSet that runs in $T(k)cdot{n}^{o(k)}$ time. $$ Assuming the Strong Exponential Time Hypothesis (SETH), for every integer $kgeq2$, there is no $F(k)$-approximation algorithm for $k$-DomSet that runs in $T(k)cdot{n}^{k-varepsilon}$ time. $$ Assuming the $k$-Sum Hypothesis, for every integer $kgeq3$, there is no $F(k)$-approximation algorithm for $k$-DomSet that runs in $T(k)cdot{n}^{lceilk/2ceil-varepsilon}$ time. Our results are obtained by establishing a connection between communication complexity and hardness of approximation, generalizing the ideas from a recent breakthrough work of Abboud et al. [FOCS 2017]. Specifically, we show that to prove hardness of approximation of a certain parameterized variant of the label cover problem, it suffices to devise a specific protocol for a communication problem that depends on which hypothesis we rely on. Each of these communication problems turns out to be either a well studied problem or a variant of one; this allows us to easily apply known techniques to solve them.

Recommendations

• On the Parameterized Complexity of Approximating Dominating Set
• The constant inapproximability of the parameterized dominating set problem
• Parameterized approximation of dominating set problems
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• Fixed-Parameter and Approximation Algorithms: A New Look

Cited in

(32)

• Structural parameterizations of dominating set variants
• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• The inapproximability of \(k\)-dominatingSet for parameterized \(\mathsf{{AC}^0}\) circuits
• On the complexity of Mixed Dominating Set
• New results on polynomial inapproximability and fixed parameter approximability of Edge Dominating Set
• Dual parameterization and parameterized approximability of subset graph problems
• A decidability result for the dominating set problem
• Approximation algorithms for connected dominating sets
• The constant inapproximability of the parameterized dominating set problem
• scientific article; zbMATH DE number 2172821 (Why is no real title available?)
• Constant-Factor FPT Approximation for Capacitated k-Median
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• Classical algorithms from quantum and Arthur-Merlin communication protocols
• scientific article; zbMATH DE number 7561535 (Why is no real title available?)
• A Simple Gap-Producing Reduction for the Parameterized Set Cover Problem
• From gap-exponential time hypothesis to fixed parameter tractable inapproximability: clique, dominating set, and more
• On the Parameterized Complexity of Approximating Dominating Set
• Lossy kernels for connected dominating set on sparse graphs
• Parameterized Complexity of Generalized Domination Problems
• Approximation Algorithms and Hardness for Domination with Propagation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• Upper dominating set: tight algorithms for pathwidth and sub-exponential approximation
• On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
• On the parameterized complexity of compact set packing
• On the parameterized complexity of compact set packing
• Parameterized inapproximability for Steiner orientation by gap amplification
• On the complexity of fixed parameter clique and dominating set
• Fine-grained hardness for edit distance to a fixed sequence
• Optimal fine-grained hardness of approximation of linear equations
• Fine-grained complexity of multiple domination and dominating patterns in sparse graphs
• Dominating set with quotas: balancing coverage and constraints
• Parameterized approximation of dominating set problems

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

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