Record Details

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

BRICS Report Series

View Archive Info
 
 
Field Value
 
Title Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)
 
Creator Grable, David A.
Panconesi, Alessandro
 
Description Vertex colouring is a much studied problem in combinatorics and computer science for its theoretical as well as its practical aspects. In this paperwe 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 thanDelta 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 proceedsin 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 becomesfinal 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 compositionof the initial lists, and does so in O(log n) rounds with highprobability|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 eachvertex 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 awakeswith 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 performanceas the trivial algorithm, but its analysis just needs pairwise independence.Luby used this fact to carry out a derandomization procedurein the pram model. Can better colourings|i.e. colourings using fewer colours|be computedeciently in a distributed setting? In 1948 Brooks gave a theoremthat 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 distributedversion 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 operationalong an \augmenting" path of length O(log n) starting from theuncoloured 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) tozero as the number of vertices grows [1, 18]. In a 1968 paper Vizing asked whether upper bounds for the chromaticnumber 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 trianglefreegraphs using signicantly fewer than colours as Brooks-Vizingcolourings. This existential problem was settled about two decades later. A. Johansson[9] showed that every triangle-free graph has chromatic numberO(= 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 smallestcycle 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 theprobability 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 theyproduce 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 thedozing-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 thetrivial one from that point on. For the general triangle-free (girth 4) case, the algorithm adds a mechanism which forces the vertex degreesof the uncoloured portion of the graph to remain roughly regular. This regularity is extremely useful in the analysis, but unfortunately givesthe algorithm a somewhat high message and space complexity. It may be, however, that this mechanism is unnecessary. The simplicity of thealgorithms 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 aremuch 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 almostalways 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 algorithmwhich, for any triangle-free, D-regular input graph G such thatD log1+ n, where > 0 is any xed constant, computes with probability1−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 Ok + 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 functionsgoing 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 anyconstant, 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 thealgorithm will compute a (D=p log n)-colouring in O(p log n) rounds. Noticealso 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 thantheir 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 onlarge 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 abstractwe 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).
 
Publisher Aarhus University
 
Date 1997-06-07
 
Type info:eu-repo/semantics/article
info:eu-repo/semantics/publishedVersion
 
Format application/pdf
 
Identifier https://tidsskrift.dk/brics/article/view/18963
10.7146/brics.v4i37.18963
 
Source BRICS Report Series; No 37 (1997): RS-37 Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)
BRICS Report Series; Nr. 37 (1997): RS-37 Fast Distributed Algorithms for Brooks-Vizing Colourings (Extended Abstract)
1601-5355
0909-0878
 
Language eng
 
Relation https://tidsskrift.dk/brics/article/view/18963/16602