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 setset coverparameterized inapproximability

Mathematics Subject Classification ID

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

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

(31)

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

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)