Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
Mohsen Ghaffari, Fabian Kühn
Abstract
We present a simple deterministic distributed algorithm that computes a ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta+1$</tex> )-vertex coloring in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}^{2}\Delta. \text{log}\ n)$</tex> rounds. The algorithm can be implemented with <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}\ n)$</tex> -bit messages. The algorithm can also be extended to the more general ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$degree+1$</tex> )-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta +1$</tex> )-vertex coloring had remained a central open question in the area of distributed graph algorithms since the 1980s, until a recent network decomposition algorithm of Rozhoň and Ghaffari [STOC'20]. The current state of the art is based on an improved variant of their decomposition, which leads to an <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}^{5}n)$</tex> -round algorithm for ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta+1$</tex> )-vertex coloring. Our coloring algorithm is completely different and considerably simpler and faster. It solves the coloring problem in a direct way, without using network decomposition, by gradually rounding a certain fractional color assignment until reaching an integral color assignments. Moreover, via the approach of Chang, Li, and Pettie [STOC'18], this improved deterministic algorithm also leads to an improvement in the complexity of randomized algorithms for ( <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta +1$</tex> )-coloring, now reaching the bound of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}^{3}\text{log}\ n)$</tex> rounds. As a further application, we provide faster deterministic distributed algorithms for the following vertex coloring variants. In graphs of arboricity <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$a$</tex> , we show that a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(2+\varepsilon)a$</tex> -vertex coloring can be computed in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}^{3}a\cdot \text{log} n)$</tex> rounds. We also show that for <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta\geq 3$</tex> , a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta$</tex> -coloring of a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Delta$</tex> -colorable graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G$</tex> can be computed in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$O(\text{log}^{2}\Delta\cdot \text{log}^{2}n)$</tex> rounds.