A local approximation algorithm for minimum dominating set problem in anonymous planar networks
A dominating set \(D \subseteq V\) in agraph \(G=(V,E)\) is asubset of vertices such that every vertex in V belongs to D or has at least one neighbour in D. In this paper we deal with the problem of finding an approximation of the dominating set of minimum size, i.e., the approximation of the minimum dominating set problem (MDS) in adistributed setting. A distributed algorithm that runs in aconstant number of rounds, independent of the size of the network, is called local. In research on distributed local algorithms it is commonly assumed that each vertex has an unique identifier. However, as was shown by Gs et al., for certain classes of graphs (for example, lift-closed bounded degree graphs) identifiers are unnecessary and only aport numbering is needed. We confirm that the same remains true for the MDS up to aconstant factor in the class of planar graphs. Namely, we present alocal deterministic 694-approximation algorithm for the MDS in planar graphs in amodel with aport numbering only. Moreover, our algorithm uses only short messages, i.e., in each round each node can send only a \(O(\log {|V|})\)-bit message to each of its neighbours.
approximation dominating set local algorithm planar graph