M. Åstrand, V. Polishchuk, J. Rybicki, J. Suomela, J. Uitto: Local algorithms in (weakly) coloured graphs

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.

Authors:	Matti Åstrand, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto
Title:	Local algorithms in (weakly) coloured graphs
Date:	January 2010
Links:	manuscript
	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.