论文标题
确定性分布式顶点着色：更简单，更快，没有网络分解
Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition
论文作者
论文摘要
我们提出了一种简单的确定性分布式算法，该算法计算$ O（\ log^2Δ\ cdot \ log n）$ roughs中的$（δ+1）$ - 顶点着色。可以使用$ O（\ log n）$ - 位消息实现该算法。该算法也可以扩展到更通用的$（度+1）$ - 列表着色问题。 自1980年代以来，在分布式图算法的领域中，以$（δ+1）$（δ+1）$（δ+1）$（δ+1）$（δ+1）的确定性算法一直是一个核心问题，直到最近的网络分解算法是Rozhoň和Ghaffari [Stoc'20]。目前的艺术状态基于其分解的改进变体，这导致$ O（\ log^5 n）$ - 圆形算法，$（δ+1）$ - 顶点颜色。 我们的着色算法是完全不同的，并且更简单，更快。它通过逐渐舍入某个部分颜色分配，直到达到积分颜色分配，以直接方式解决着色问题，而无需使用网络分解。此外，通过Chang，Li和Pettie [Stoc'18]的方法，这改进了确定性算法，还可以改善$（δ+1）$ - 着色的随机算法的复杂性，现在达到了$ O（\ log log^log^3 \ log n）$ nounds $。 作为进一步的应用程序，我们还为顶点着色问题的以下变体提供了更快的确定性分布式算法。在Arboricity $ a $的图表中，我们表明$（2+ε）可以以$ o（\ log^3 a \ cdot \ log n）$ rounds计算$ vertex着色。我们还表明，对于$δ\ geq 3 $，可以以$ o（\ log^2δ\ cdot \ log^2 n）$ rounds计算$δ$ - 可油的$δ$颜色。
We present a simple deterministic distributed algorithm that computes a $(Δ+1)$-vertex coloring in $O(\log^2 Δ\cdot \log n)$ rounds. The algorithm can be implemented with $O(\log n)$-bit messages. The algorithm can also be extended to the more general $(degree+1)$-list coloring problem. Obtaining a polylogarithmic-time deterministic algorithm for $(Δ+1)$-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 $O(\log^5 n)$-round algorithm for $(Δ+1)$-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 $(Δ+1)$-coloring, now reaching the bound of $O(\log^3\log n)$ rounds. As a further application, we also provide faster deterministic distributed algorithms for the following variants of the vertex coloring problem. In graphs of arboricity $a$, we show that a $(2+ε)a$-vertex coloring can be computed in $O(\log^3 a\cdot\log n)$ rounds. We also show that for $Δ\geq 3$, a $Δ$-coloring of a $Δ$-colorable graph $G$ can be computed in $O(\log^2 Δ\cdot\log^2 n)$ rounds.
