A strengthened analysis of a local algorithm for the minimum dominating set problem in planar graphs

• We improve an analysis of algorithm from paper “What can be approximated locally? Case study: Dominating Set”.
• We simplify analysis of local algorithm for Minimal Dominating Set Problem in planar graphs.
• We reduced the gap between the lower bound and the best so far deterministic local algorithm by half, which now comes to 52.

In recent years growing interest in local distributed algorithms has widely been observed. This results from their high resistance to errors and damage, as well as from their good performance, which is independent of the size of the network. A local deterministic distributed algorithm finding an approximation of a Minimum Dominating Set in planar graphs has been presented by Lenzen et al., and they proved that the algorithm returns a 130-approximation of the Minimum Dominating Set. In this article we will show that the algorithm is two times more effective than was previously assumed, and we prove that the algorithm by Lenzen et al. outputs a 52-approximation to a Minimum Dominating Set. Therefore the gap between the lower bound and the approximation ratio of the best yet local deterministic distributed algorithm is reduced by half.