PODC 2012 · 31st Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Madeira, Portugal, July 2012 · doi:10.1145/2332432.2332465

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 and by prior work, we derive a tight lower bound on the local approximability of the *minimum edge dominating set problem*.

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

Darek Kowalski and Alessandro Panconesi (Eds.): *PODC’12, Proceedings of the 2012 ACM Symposium on Principles of Distributed Computing, July 16–18, 2012, Madeira, Portugal*, pages 175–184, ACM Press, New York, 2012

ISBN 978-1-4503-1450-3

- Mika Göös, Juho Hirvonen, and Jukka Suomela: Lower bounds for local approximation ·
*Journal of the ACM*60:#39, 2013