Almost tight distributed approximation for domination in sparse graph classes

Abstract

We study distributed approximation of Minimum Dominating Set in a very general class of sparse graphs, extending near-optimal approximation results from the minor-free setting to bounded expansion. In more detail, for fixed $d$ and $\epsilon >0$, we give a new deterministic constant-round LOCAL algorithm for Minimum Dominating Set on graphs of maximum average degree at most $d$ and bounded depth-one shallow-minor density. Its approximation ratio is $d+1+\epsilon$, which is optimal up to $\epsilon$ for every even integer $d\ge 2$. This improves on the recent results of Amiri and Siebertz by extending beyond proper minor-closed classes. From this algorithm, we derive almost-tight constant-round approximations for a number of graph classes. We get $(7+\epsilon )$-approximations for planar graphs and graphs of bounded Euler genus, and $(5+\epsilon )$-approximations for their triangle-free subclasses. This answers the $7+\epsilon$ question of Wawrzyniak positively, and matches the recent results of Amiri and Siebertz. We also apply our algorithm to classes of bounded queue-number or stack-number, obtaining bounds that are tight up to $\epsilon$. Additionally, we answer questions of Amiri and Siebertz about improving the dependence of the round complexity on $1/\epsilon$ and obtaining polynomial local computation for fixed parameters, when comparing the output to the usual domination number.

arXiv comment27 pages, 4 figures