Lower bounds for local approximation
Mika Göös, Juho Hirvonen, Jukka Suomela · Journal of the ACM · 2013
In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique O (log n )-bit identifier. We prove that for a general class of graph problems, local algorithms (constant-time distributed algorithms) do not need such identifiers: a port numbering and orientation is sufficient. Our result holds for so-called simple PO- checkable graph optimisation problems ; this includes many classical packing and covering problems such as vertex covers, edge covers, matchings, independent sets, dominating sets, and edge dominating sets. We focus on the case of bounded-degree graphs and show that if a local algorithm finds a constant-factor approximation of a simple PO-checkable graph problem with the help of unique identifiers, then the same approximation ratio can be achieved on anonymous networks. As a corollary of our result, we derive a tight lower bound on the local approximability of the minimum edge dominating set problem . By prior work, there is a deterministic local algorithm that achieves the approximation factor of 4--1/⌊Δ/2⌋ in graphs of maximum degree Δ. This approximation ratio is known to be optimal in the port-numbering model—our main theorem implies that it is optimal also in the standard model in which each node has a unique identifier. Our main technical tool is an algebraic construction of homogeneously ordered graphs : We say that a graph is (α, r )-homogeneous if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic radius- r neighbourhoods. We show that there exists a finite (α, r )-homogeneous 2 k -regular graph of girth at least g for any α < 1 and any r , k , and g .