Kernelization and Sparseness: the case of Dominating Set

DOI10.4230/LIPICS.STACS.2016.31MaRDI QIDQ4601883zbMATH OpenOpenAlexFDO

Authors

Publication date 24 January 2018

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

zbMATH Keywords

bounded expansiondominating setkernelizationnowhere dense

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Abstract: We prove that for every positive integer $r$ and for every graph class $mathcalG$ of bounded expansion, the $r$-Dominating Set problem admits a linear kernel on graphs from $mathcalG$. Moreover, when $mathcalG$ is only assumed to be nowhere dense, then we give an almost linear kernel on $mathcalG$ for the classic Dominating Set problem, i.e., for the case $r=1$. These results generalize a line of previous research on finding linear kernels for Dominating Set and $r$-Dominating Set. However, the approach taken in this work, which is based on the theory of sparse graphs, is radically different and conceptually much simpler than the previous approaches. We complement our findings by showing that for the closely related Connected Dominating Set problem, the existence of such kernelization algorithms is unlikely, even though the problem is known to admit a linear kernel on $H$-topological-minor-free graphs. Also, we prove that for any somewhere dense class $mathcalG$, there is some $r$ for which $r$-Dominating Set is W[$2$]-hard on $mathcalG$. Thus, our results fall short of proving a sharp dichotomy for the parameterized complexity of $r$-Dominating Set on subgraph-monotone graph classes: we conjecture that the border of tractability lies exactly between nowhere dense and somewhere dense graph classes.

Recommendations

• scientific article; zbMATH DE number 7764102
• On kernelization for edge dominating set under structural parameters
• Lossy kernels for connected dominating set on sparse graphs
• Lossy kernels for connected dominating set on sparse graphs
• A linear kernel for planar total dominating set
• The effect of girth on the kernelization complexity of connected dominating set
• Kernels for edge dominating set: simpler or smaller
• A linear kernel for a planar connected dominating set
• A metric approach to sparse domination
• Kernelization and Lower Bounds of the Signed Domination Problem

Cited in

(48)

• Characterising bounded expansion by neighbourhood complexity
• Reconfiguration on nowhere dense graph classes
• On directed covering and domination problems
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Twin-width and polynomial kernels
• Constant round distributed domination on graph classes with bounded expansion
• Improved bounds for weak coloring numbers
• On the parameterized complexity of the expected coverage problem
• A metric approach to sparse domination
• Harmless sets in sparse classes
• On approximate preprocessing for domination and hitting subgraphs with connected deletion sets
• Linear kernels for outbranching problems in sparse digraphs
• Kernelization and approximation of distance-r independent sets on nowhere dense graphs
• Bounds on half graph orders in powers of sparse graphs
• Minimum fill-in of sparse graphs: kernelization and approximation
• Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm
• Lossy kernels for connected dominating set on sparse graphs
• Bidimensionality and kernels
• Kernelization using structural parameters on sparse graph classes
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Polynomial kernels and wideness properties of nowhere dense graph classes
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• On the Parameterized Complexity of the Expected Coverage Problem
• Operator-free sparse domination
• Progressive algorithms for domination and independence
• Algorithmic properties of sparse digraphs
• Domination above \(r\)-independence: does sparseness help?
• Lossy Kernels for Hitting Subgraphs
• scientific article; zbMATH DE number 7204413 (Why is no real title available?)
• On directed covering and domination problems
• Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
• Lossy kernels for connected dominating set on sparse graphs
• On the generalised colouring numbers of graphs that exclude a fixed minor
• scientific article; zbMATH DE number 7764102 (Why is no real title available?)
• scientific article; zbMATH DE number 7764115 (Why is no real title available?)
• Hardness of the generalized coloring numbers
• Distributed domination on sparse graph classes
• Sunflowers meet sparsity: a linear-vertex kernel for weighted clique-packing on sparse graphs
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• Data reduction for directed feedback vertex set on graphs without long induced cycles. Three rules to rule them all
• Parameterized complexity of (d, r)-domination via modular decomposition
• A survey on the parameterized complexity of reconfiguration problems
• Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
• The tape reconfiguration problem and its consequences for dominating set reconfiguration
• On the parameterized complexity of reconfiguration of connected dominating sets
• Sublinear separators, fragility and subexponential expansion

This page was built for publication: Kernelization and Sparseness: the case of Dominating Set

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