Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)

Abstract

Vertex colouring is a much studied problem in combinatorics and computer science for its theoretical as well as its practical aspects. In this paper
we are concerned with the "distributed" version of a question stated by Vizing, concerning a Brooks-like theorem for sparse graphs. Roughly, the question asks whether there exist colourings using many fewer than
Delta colours, where Delta denotes the maximum degree of the graph, provided that some sparsity conditions are satisfied. In this paper we show that such colourings not only exist, but that they can be quickly computed by extremely simple distributed, randomized algorithms. Before stating our results precisely, we review the relevant facts. For any graph G of maximum degree with n vertices, the following trivial algorithm computes a Delta+1 (list) colouring. Each vertex u initially has a list, or palette, of deg(u) + 1 colours. The computation proceeds
in rounds. During each round, each uncoloured vertex, in parallel, first performs a trivial attempt: it picks a tentative colour at random from its palette and if no neighbour picks the same colour, the colour becomes
final and the algorithm stops for that vertex. Otherwise, the vertex's palette undergoes a trivial update - the colours succesfully used by the neigbours are removed - and a new attempt is performed in the next round.
Henceforth we shall refer to this as "the" trivial algorithm. The trivial algorithm always computes a valid colouring regardless of the composition
of the initial lists, and does so in O(log n) rounds with high
probability|that is, with probability approaching 1 as the number of vertices increases [10, 13, 4].
It is apparent that the trivial algorithm is distributed, since each
vertex only relies on information from the neighbouring vertices. The well-known distributed algorithm for the same problem given by Luby [15] amends the trivial algorithm in the following way: at the beginning of each round every uncoloured vertex is asleep. Each such vertex awakes
with probability p and executes a trivial attempt (in Luby's paper p = 1/2). Then, whether or not the vertex awoke, the palette undergoes a trivial update. At the end of the round the vertex goes back to sleep.

We shall refer to this variant of the trivial algorithm as the dozing-off algorithm. The dozing-off algorithm has the same asymptotic performance
as the trivial algorithm, but its analysis just needs pairwise independence.
Luby used this fact to carry out a derandomization procedure
in the pram model. Can better colourings|i.e. colourings using fewer colours|be computed
eciently in a distributed setting? In 1948 Brooks gave a theorem
that characterizes the graphs which are not {colourable: a graph is
{colourable if and only if it is neither an odd cycle nor a + 1 clique (see, for instance, [2]).
The proof of Brooks' theorem is actually a polynomial time sequential algorithm. {colourings can also be quickly (i.e. in polylogarithmic time) computed in the PRAM model [8, 11, 12]. In fact, a distributed
version of Brooks' theorem can be derived from a certain locality property of -colourings, yielding the following: There is no o(n) randomized, synchronous protocol to -colour paths, cycles or cliques. For all other graphs, there is a randomized protocol which, with high probability, computes a -colouring in polylogarithmically many rounds [17].
(The property in question, holding for graphs which are neither cliques, paths nor cycles, is this: If G is {coloured except for one last vertex, it is possible to complete the colouring by a simple recolouring operation
along an \augmenting" path of length O(log n) starting from the
uncoloured vertex [17].)
It is an open problem whether randomization is necessary in all of the above algorithmic results; the asymptotically best deterministic protocols known to date need O(n(n)) rounds, where (n) tends (very slowly) to
zero as the number of vertices grows [1, 18]. In a 1968 paper Vizing asked whether upper bounds for the chromatic
number better than those given by Brooks' Theorem existed, provided some sparsity conditions were satised. In particular, he asked what happens for triangle-free graphs. We shall refer to colourings of trianglefree
graphs using signicantly fewer than colours as Brooks-Vizing
colourings. This existential problem was settled about two decades later. A. Johansson
[9] showed that every triangle-free graph has chromatic number
O(= log). This is best-possible up to a constant factor, since Bollobas had shown the existence of graphs with arbitrarily high girth such that
(G) =  (=log) (the girth of a graph G is the size of the smallest
cycle therein) [3]. Johansson's result, as well as an earlier result of Kim [14], which shows that graphs of girth at least 5 have chromatic number (1+o(1))= log, make use of certain distributed colouring algorithms, but their results are only existential in the following sense. They show only that the
probability that the algorithm produces a valid colouring is positive.
Their analyses do not rule out the possibility of their algorithms failing with a high probability. (But then, this was not their main concern.) In this paper, we show that Brooks-Vizing colourings can be computed eciently even in a distributed setting. We present very simple randomized, distributed algorithms, which are also easily implementable on a pram and in the sequential setting, and demonstrate that they
produce the desired colourings with high probability.
Our algorithms are variants of the dozing-o algorithm. In fact, when the input graph has no 4-cycles (girth 5 or greater) the algorithm is the
dozing-o algorithm modied so that the probability that vertices awake is not constant but varies with the round. This probability, initially very low, quickly rises to one, causing the algorithm to be behave as the
trivial one from that point on. For the general triangle-free (girth 4) case, the algorithm adds a mechanism which forces the vertex degrees
of the uncoloured portion of the graph to remain roughly regular. This regularity is extremely useful in the analysis, but unfortunately gives
the algorithm a somewhat high message and space complexity. It may be, however, that this mechanism is unnecessary. The simplicity of the
algorithms is an appealing feature and we expect them to work quite well in practice.
Although these algorithms display similarities to those in Kim's work [14], we have striven for speed and simplicity. Moreover, our analyses are
much simpler than those given there. It is perhaps worth remarking that our analyses demonstrate that Brooks-Vizing colourings are not rare, for the randomized colour assignments computed by the algorithm almost
always produces such a colouring. Furthermore, they highlight the role played by the girth assumption. Our result may be conveniently stated as follows: We give an algorithm
which, for any triangle-free, D-regular input graph G such that
D log1+ n, where > 0 is any xed constant, computes with probability
1−o(1) a vertex colouring of G using D=k colours, for any k logD, where is a constant which depends on . Moreover, with probability 1 − o(1), the colouring will be completed within O
k + log n logD
rounds in the synchronous, message-passing distributed model of computation
(with no shared memory). Both of the above o(1) terms are functions
going to 0 with n, the number of vertices in the network.
The statement of the theorem allows some flexibility in the choice of k and D. For instance, by choosing D nc= log log n, where c > 1 is any
constant, and k = log log n, the algorithm will compute a (D= log log n)-
colouring in just O(log log n) rounds. Or, by choosing D nc=
p log n the
algorithm will compute a (D=
p log n)-colouring in O(
p log n) rounds. Notice
also that the algorithm works for k =  (logD), thereby matching the lower bounds of Bollobas and the existential statements of Johansson and Kim. It should be pointed out however that our statement is weaker than
their existential statement insofar as it needs the additional assumption D =  (logn). This, as well as the regularity assumption (also assumed in [9, 14]), might in fact be an artifact of our analysis which relies on
large deviation inequalities that cease to give strong enough bounds for lower values of D. Although we stated our result in its most general form, in this abstract
we shall present a slightly weaker version, due to lack of space. Namely, we shall show that the above statement holds with the running timereplaced by O(log n).