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
(39)- Towards a characterization of universal categories
- Packing and covering balls in graphs excluding a minor
- Twin-width and generalized coloring numbers
- Improved bounds for weak coloring numbers
- A metric approach to sparse domination
- Harmless sets in sparse classes
- On coloring numbers of graph powers
- Edge degeneracy: algorithmic and structural results
- Uniform orderings for generalized coloring numbers
- VC-dimension and Erdős-Pósa property
- Kernelization and approximation of distance-r independent sets on nowhere dense graphs
- Colouring and covering nowhere dense graphs
- Digraphs of bounded width
- Coloring and covering nowhere dense graphs
- Empirical Evaluation of Approximation Algorithms for Generalized Graph Coloring and Uniform Quasi-wideness
- Algorithmic properties of sparse digraphs
- 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
- On the generalised colouring numbers of graphs that exclude a fixed minor
- A distributed low tree-depth decomposition algorithm for bounded expansion classes
- On weighted sublinear separators
- scientific article; zbMATH DE number 7764102 (Why is no real title available?)
- Shallow Minors, Graph Products, and Beyond-Planar Graphs
- A color-avoiding approach to subgraph counting in bounded expansion classes
- Bounding generalized coloring numbers of planar graphs using coin models
- Hardness of the generalized coloring numbers
- Distributed domination on sparse graph classes
- Discrepancy and sparsity
- Twin-width. III: Max independent set, min dominating set, and coloring
- On classes of bounded tree rank, their interpretations, and efficient sparsification
- Cop-width, flip-width and strong colouring numbers
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Turbocharging heuristics for weak coloring numbers
- Unified almost linear kernels for generalized covering and packing problems on nowhere dense classes
- Shallow brambles
- Results on H-freeness testing in graphs of bounded r-admissibility
- Defective and clustered colouring of graphs with given girth
- Testing C_k-freeness in bounded admissibility graphs
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)
