### Lower bounds for local approximationLower bounds for local approximation

Access Restriction
Subscribed

 Author Gs, Mika ♦ Hirvonen, Juho ♦ Suomela, Jukka Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2013 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Deterministic distributed algorithms ♦ Edge dominating set ♦ Local algorithms ♦ Unique identifiers Abstract In the study of deterministic distributed algorithms, it is commonly assumed that each node has a unique $\textit{O}(log$ $\textit{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 $\textit{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 $(α,\textit{r})-homogeneous$ if its nodes are linearly ordered so that an α fraction of nodes have pairwise isomorphic $radius-\textit{r}$ neighbourhoods. We show that there exists a finite $(α,\textit{r})-homogeneous$ $2\textit{k}-regular$ graph of girth at least $\textit{g}$ for any α < 1 and any $\textit{r},$ $\textit{k},$ and $\textit{g}.$ ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2013-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 60 Issue Number 5 Page Count 23 Starting Page 1 Ending Page 23

#### Open content in new tab

Source: ACM Digital Library