Constant-factor approximation of the domination number in sparse graphs
From MaRDI portal
Abstract: The k-domination number of a graph is the minimum size of a set X such that every vertex of G is in distance at most k from X. We give a linear time constant-factor approximation algorithm for k-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, classes closed on topological minors or classes of graphs that can be drawn on a fixed surface with bounded number of crossings on each edge. The algorithm is based on the following approximate min-max characterization. A subset A of vertices of a graph G is d-independent if the distance between each pair of vertices in A is greater than d. Note that the size of the largest 2k-independent set is a lower bound for the k-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k-independent set A and a k-dominating set D such that |D|=O(|A|), and these sets can be found in linear time. For domination number (k=1) the assumptions can be relaxed, and the result holds for all graph classes with arrangeability bounded by a constant.
Recommendations
- On distance \(r\)-dominating and \(2r\)-independent sets in sparse graphs
- Distributed approximation algorithms for k-dominating set in graphs of bounded genus and linklessly embeddable graphs
- On constant time approximation of parameters of bounded degree graphs
- FPT algorithms for domination in sparse graphs and beyond
- Approximations of the domination number of a graph
Cited in
(30)- Coloring and covering nowhere dense graphs
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- Improved bounds for weak coloring numbers
- Lossy kernels for connected dominating set on sparse graphs
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- VC-dimension and Erdős-Pósa property
- Uniform orderings for generalized coloring numbers
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Kernelization and approximation of distance-\(r\) independent sets on nowhere dense graphs
- Empirical evaluation of approximation algorithms for generalized graph coloring and uniform quasi-wideness
- On coloring numbers of graph powers
- Colouring and covering nowhere dense graphs
- A color-avoiding approach to subgraph counting in bounded expansion classes
- Distributed domination on sparse graph classes
- Hardness of the generalized coloring numbers
- Discrepancy and sparsity
- Algorithmic properties of sparse digraphs
- Towards a characterization of universal categories
- On weighted sublinear separators
- Bounding generalized coloring numbers of planar graphs using coin models
- Twin-width. III: Max independent set, min dominating set, and coloring
- Harmless sets in sparse classes
- A metric approach to sparse domination
- Twin-width and generalized coloring numbers
- On the generalised colouring numbers of graphs that exclude a fixed minor
- Packing and covering balls in graphs excluding a minor
- Edge degeneracy: algorithmic and structural results
- Digraphs of bounded width
- On the generalised colouring numbers of graphs that exclude a fixed minor
This page was built for publication: Constant-factor approximation of the domination number in sparse graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1943391)
