  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.

Combinatorics;Data Structures and Algorithms