Matti Åstrand · Valentin Polishchuk · Joel Rybicki · Jukka Suomela · Jara Uitto

Local algorithms in (weakly) coloured graphs

Manuscript · January 2010

authors’ version arXiv.org

Abstract

A local algorithm is a distributed algorithm that completes after a constant number of synchronous communication rounds. We study local approximation algorithms for the minimum dominating set problem and the maximum matching problem in 2-coloured and weakly 2-coloured graphs. We show that in a weakly 2-coloured graph, both problems admit a local algorithm with the approximation factor (Δ + 1)/2, where Δ is the maximum degree of the graph. We also give a matching lower bound proving that there is no local algorithm with a better approximation factor for either of these problems. Furthermore, we show that the stronger assumption of a 2-colouring does not help in the case of the dominating set problem, but there is a local approximation scheme for the maximum matching problem in 2-coloured graphs.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.