Kernelization and Sparseness: the case of Dominating Set

DOI10.4230/LIPICS.STACS.2016.31zbMATH Open1388.68110arXiv1411.4575OpenAlexW2963587624MaRDI QIDQ4601883FDOQ4601883

Author name not available (Why is that?)

Publication date: 24 January 2018

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.

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

Recommendations

• scientific article; zbMATH DE number 7764102
• scientific article; zbMATH DE number 7559145
• 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

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)

Cited In (40)

• Decremental Optimization of Dominating Sets Under the Reconfiguration Framework
• On the parameterized complexity of reconfiguration of connected dominating sets
• Title not available (Why is that?)
• Operator-free sparse domination
• Title not available (Why is that?)
• Improved bounds for weak coloring numbers
• Title not available (Why is that?)
• On the Parameterized Complexity of the Expected Coverage Problem
• On directed covering and domination problems
• Title not available (Why is that?)
• On the parameterized complexity of the expected coverage problem
• Characterising bounded expansion by neighbourhood complexity
• Reconfiguration on nowhere dense graph classes
• Bidimensionality and Kernels
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
• Parameterized algorithms for Max Colorable Induced Subgraph problem on perfect graphs
• Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
• Kernelization using structural parameters on sparse graph classes
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• Minimum fill-in of sparse graphs: kernelization and approximation
• Distributed domination on sparse graph classes
• Hardness of the generalized coloring numbers
• Sublinear separators, fragility and subexponential expansion
• Lossy Kernels for Connected Dominating Set on Sparse Graphs
• 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
• On Directed Covering and Domination Problems
• Bounds on half graph orders in powers of sparse graphs
• Lossy Kernels for Hitting Subgraphs
• Title not available (Why is that?)
• Solving Dominating Set in Larger Classes of Graphs: FPT Algorithms and Polynomial Kernels
• Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-Wideness
• Title not available (Why is that?)
• 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
• Reconfiguration on sparse graphs

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)