Lossy kernels for connected dominating set on sparse graphs

DOI10.4230/LIPICS.STACS.2018.29MaRDI QIDQ3304128zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, Sebastian Siebertz

Publication date 5 August 2020

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

zbMATH Keywords

connected dominating setlossy kernelizationsparse graph classes

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Abstract: For $alpha>1$, an $alpha$-approximate (bi-)kernel is a polynomial-time algorithm that takes as input an instance $(I,k)$ of a problem $mathcalQ$ and outputs an instance $(I^{\prime },k^{\prime })$ (of a problem $mathcal{Q}^{\prime }$) of size bounded by a function of $k$ such that, for every $cgeq1$, a $c$-approximate solution for the new instance can be turned into a $(ccdotalpha)$-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov et al. We study Connected Dominating Set (and its distance-$r$ variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every $alpha>1$, Connected Dominating Set admits a polynomial-size $alpha$-approximate (bi-)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on $2$-degenerate graphs and graphs of bounded expansion, unless $extsfNPsubseteqextsfcoNP/poly$. We complement our results by the following conditional lower bound. We show that if a class $mathcalC$ is somewhere dense and closed under taking subgraphs, then for some value of $rinmathbbN$ there cannot exist an $alpha$-approximate bi-kernel for the (Connected) Distance-$r$ Dominating Set problem on $mathcalC$ for any $alpha>1$ (assuming the Gap Exponential Time Hypothesis).

Recommendations

• Lossy kernels for connected dominating set on sparse graphs
• Lossy Kernels for Hitting Subgraphs
• Kernelization and Sparseness: the case of Dominating Set
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Lossy kernelization

Cites work

• (Meta) Kernelization
• A combinatorial problem; stability and order for models and theories in infinitary languages
• A linear kernel for a planar connected dominating set
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Bidimensionality and kernels
• Domination problems in nowhere-dense classes of graphs
• First order properties on nowhere dense structures
• Fourier meets M\"{o}bius: fast subset convolution
• FPT algorithms for connected feedback vertex set
• Fundamentals of parameterized complexity
• Grad and classes with bounded expansion. I: Decompositions
• Grad and classes with bounded expansion. II: Algorithmic aspects
• Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
• Graph Classes: A Survey
• scientific article; zbMATH DE number 6678911 (Why is no real title available?)
• Kernelization and Sparseness: the case of Dominating Set
• Kernelization hardness of connectivity problems in \(d\)-degenerate graphs
• Kernelization using structural parameters on sparse graph classes
• Linear kernels for (connected) dominating set on \(H\)-minor-free graphs
• Lossy kernelization
• Neighborhood complexity and kernelization for nowhere dense classes of graphs
• On nowhere dense graphs
• On the density of families of sets
• Parameterized algorithms
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Polynomial kernels for \textsc{Dominating Set} in graphs of bounded degeneracy and beyond
• Polynomial-time data reduction for dominating set
• Sparsity. Graphs, structures, and algorithms
• Tight Kernel Bounds for Problems on Graphs with Small Degeneracy

Cited in

(14)

• Lossy kernelization of same-size clustering
• On the parameterized complexity of \([1,j]\)-domination problems
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Kernelization and Sparseness: the case of Dominating Set
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Parameterized approximation algorithms for bidirected Steiner network problems
• An approximate kernel for connected feedback vertex set
• Algorithmic properties of sparse digraphs
• On the Parameterized Complexity of [1,j]-Domination Problems
• Lossy Kernels for Hitting Subgraphs
• Lossy kernels for connected dominating set on sparse graphs
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• On approximate data reduction for the Rural Postman Problem: Theory and experiments
• On the parameterized complexity of reconfiguration of connected dominating sets

This page was built for publication: Lossy kernels for connected dominating set on sparse graphs

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