Local Approximability of Minimum Dominating Set on Planar Graphs
Miikka Hilke, Christoph Lenzen, Jukka Suomela · arXiv (Cornell University) · 2014
We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-ε)$-approximation of a minimum dominating set on planar graphs, for any positive constant $ε$. In prior work, the best lower bound on the approximation ratio has been $5-ε$; there is also an upper bound of $52$.