• Calendar

February 2, Wednesday
12:00 – 13:30

We consider the vertex coloring problem in the message-passing model of distributed computing. In this model the network is represented by a graph G of maximum degree Delta, in which the vertices host processors, and the communication is performed over the edges of G. Vertex coloring has numerous applications in communication networks, and thus it has drawn a considerable attention of researchers in the last three decades. The question of how many colors an efficient algorithm (that is, an algorithm with polylogarithmic time) is required to use is a central long-standing open question. Currently, efficient randomized algorithms that employ Delta + 1 colors are known, but it is unknown whether this number of colors can be achieved deterministically and efficiently. In 1987, in a seminal FOCS paper, Linial devised an efficient deterministic algorithm that employs Delta^2 colors. In his paper Linial also asked whether it is possible to employ a significantly smaller number of ! colors while still maintaining a deterministic algorithm with polylogarithmic running time. Despite a very intensive research in this direction in the last twenty years, this question remained open prior to our work. We present a deterministic algorithm that runs in polylogarithmic time, and employs Delta^{1 + epsilon} colors, for an arbitrarily small positive constant epsilon. Thus, our algorithm settles the long-standing question of Linial. Moreover, our results give rise to significantly improved algorithm for O(Delta)-coloring, and even for o(Delta)-coloring of very wide graph families. These results are achieved using a novel graph-decomposition technique. Specifically, the vertex set of the graph is partitioned into subsets that satisfy certain helpful properties. In particular, the subsets induce sparse subgraphs. This allows coloring the subgraphs with sufficiently small number of colors while utilizing the parallelism of the network to the full extent. Our recent results show that this technique is very powerful, and is useful for additional problems such as edge coloring.