Local Approximability of Minimum Dominating Set on Planar Graphs

Abstract. 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.