论文标题
快速分布式布鲁克斯的定理
Fast Distributed Brooks' Theorem
论文作者
论文摘要
我们在本地模型中给出了一个随机的$δ$ - 颜色算法，该算法以$ \ text {poly} \ log n $ nods运行，其中$ n $是输入图的节点的数量，$Δ$是其最高度。这意味着随机$δ$ - 颜色是一个罕见的分布式着色问题，在同一球场中具有上限和下限，$ \ text {poly} \ log \ log \ log n $，给定已知的$ω（\log_Δ\ log log n）$下限$下限[Brandt et al。，Stoc '16]。 我们的主要技术贡献是恒定的时间缩短至$（\ text {deg} +1）$ - 列表着色实例，以$δ=ω（\ log^4 n）$，从而导致$ \ text {poly} \ log \ log \ log n $ n $ - round algort concest algorite for for for thuge for for thuge tographs。这种减少对其他环境具有独立的兴趣，包括提供了布鲁克斯的高度图定理的新证明，并在此类图中导致了恒定的拥塞算法。 当$δ=ω（\ log^{21} n）$时，我们的算法甚至以$ o（\ log^* n）$ rounds运行，表明$ω（\log_δ\ log log n）$下bufter Bond BOUNT BOUNTING中的基础是不可避免的。 以前，用于所有考虑的设置的最佳本地算法都使用了对数数量的回合。我们的结果是第一个使用$δ$颜色的非稳定度图的交通拥堵算法。
We give a randomized $Δ$-coloring algorithm in the LOCAL model that runs in $\text{poly} \log \log n$ rounds, where $n$ is the number of nodes of the input graph and $Δ$ is its maximum degree. This means that randomized $Δ$-coloring is a rare distributed coloring problem with an upper and lower bound in the same ballpark, $\text{poly}\log\log n$, given the known $Ω(\log_Δ\log n)$ lower bound [Brandt et al., STOC '16]. Our main technical contribution is a constant time reduction to a constant number of $(\text{deg}+1)$-list coloring instances, for $Δ= ω(\log^4 n)$, resulting in a $\text{poly} \log\log n$-round CONGEST algorithm for such graphs. This reduction is of independent interest for other settings, including providing a new proof of Brooks' theorem for high degree graphs, and leading to a constant-round Congested Clique algorithm in such graphs. When $Δ=ω(\log^{21} n)$, our algorithm even runs in $O(\log^* n)$ rounds, showing that the base in the $Ω(\log_Δ\log n)$ lower bound is unavoidable. Previously, the best LOCAL algorithm for all considered settings used a logarithmic number of rounds. Our result is the first CONGEST algorithm for $Δ$-coloring non-constant degree graphs.
