Local Approximability of Minimum Dominating Set on Planar Graphs

Miikka Hilke, Christoph Lenzen, Jukka Suomela

We show that there is no deterministic local algorithm (constant-time distributed graph algorithm) that finds a $(7-\epsilon )$-approximation of a minimum dominating set on planar graphs,…