Constant-factor approximation of the domination number in sparse graphs

The kk-domination number   of a graph is the minimum size of a set DD such that every vertex of GG is at distance at most kk from DD. We give a linear-time constant-factor algorithm for approximation of the kk-domination number in classes of graphs with bounded expansion, which include e.g. proper minor-closed graph classes, proper classes closed on topological minors and 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 AA of vertices of a graph GG is dd-independent   if the distance between each two vertices in AA is greater than dd. Note that the size of the largest 2k2k-independent set is a lower bound for the kk-domination number. We show that every graph from a fixed class with bounded expansion contains a 2k2k-independent set AA and a kk-dominating set DD such that |D|=O(|A|)|D|=O(|A|), and these sets can be found in linear time.For a fixed value of kk, the assumptions on the class can be formulated more precisely in terms of generalized coloring numbers. In particular, for the domination number (k=1k=1), the results hold for all graph classes with arrangeability bounded by a constant.