Distributed Graph Coloring in a Few Rounds

摘要

This paper considers the question of how many colors a distributed graph coloring algorithm would need to use if it had only k rounds available, for any positive integer k. In our main result, we present an algorithm that runs in O(k) rounds for any k bounded below by Ω(log log n) and bounded above by O((log n)~(1/2)), and uses O(a · n~(1/k)) colors to color a graph with arboricity a. This result is optimal since the palette size matches the lower bound of Baren-boim and Elkin (PODC 2008). This result is achieved via the use of several new results developed in this paper on coloring graphs whose edges have been acyclically oriented. For example, suppose that G is an n-vertex, acyclically oriented graph with maximum out-degree △_o. We present an algorithm that, for any k ≥ 2 log log n, runs in O(k) rounds on G to produce an (i) O(△_o)-coloring when △_o ∈ Ω(max{kn~(2/k~2) log~(1+1/k) n, 2~k}) and an (ii) O(△_o·n~(2/k~2))-color-ing when △_o ∈ Ω(max{k log~(1+1/k) n,2~k}). These results are useful in any setting where it is possible to efficiently compute acyclic orientations of a graph with △_o (≤) △. We derive non-trivial bounds on the palette size even when k < 2 log log n. Our main technical contributions can be summarized as: (i) developing a k-round version of the algorithm of Kotha-palli et al. (IPDPS 2006) which computes an O(△)-coloring of a graph in O((log n)~(1/2)) rounds, and (ii) developing an oriented version of the Brooks-Vizing coloring result of Grable and Panconesi (SODA 1998).