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

dominating setkernelizationnowhere densebounded expansion

Mathematics Subject Classification ID

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

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

(41)

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