Near-Optimal Distributed Domination in Planar Graphs

Abstract

We give a deterministic $(8+\epsilon )$-approximation for minimum dominating set on planar graphs in a constant number of rounds of the LOCAL model, for every $\epsilon >0$. This improves the previous ratio $11+\epsilon$ obtained by Heydt et al. The ratio is near-optimal in this model: its leading constant is only one above the known lower bound of $7$. Our result closes three quarters of the previous gap, reducing it from $4$ to $1$. Our main contribution is a sharp structural bound. For any dominating set $D$, assigning each vertex outside $D$ to a neighboring center gives disjoint owner blocks. If $k_x$ counts the other blocks containing a neighbor of $x$, then ${\sum }_{x\notin D}(k_x-2{)}^{+}\le (4|D|-12{)}^{+}$, where $z^{+}=\max \{z,0\}$. The bound holds for every such assignment, and equality holds for arbitrarily large minimum dominating sets. We use this bound in their three-phase framework, with new parameters and the same final linear-programming procedure. The algorithm requires neither a planar embedding nor the graph size, and its round bound depends only on $\epsilon$. The transfer theorem of Bonamy et al. also gives a deterministic $(25+\epsilon )$-approximation on graphs of bounded Euler genus, with a round bound depending only on $\epsilon$ and the genus.

19 pages, 7 figures