The Complexity of (Δ+1) Coloring in Congested Clique, Massively Parallel Computation, and Centralized Local Computation

In this paper, we present new randomized algorithms that improve the complexity of the classic (Delta + 1)-coloring problem, and its generalization (Delta + 1)-list-coloring, in three well-studied models of distributed, parallel, and centralized computation:Distributed Congested Clique: We present an O(1)-round randomized algorithm for (Delta + 1)-list-coloring in the congested clique model of distributed computing. This settles the asymptotic complexity of this problem. It moreover improves upon the O(log*Delta)-round randomized algorithms of Parter and Su [DISC'18] and O((log log.) center dot log*Delta-round randomized algorithm of Parter [ICALP'18].Massively Parallel Computation: We present a randomized (Delta + 1)-list-coloring algorithm with round complexity O(root log logn) in the Massively Parallel Computation (MPC) model with strongly sublinear memory per machine. This algorithm uses a memory of O(n(alpha)) per machine, for any desirable constant alpha > 0, and a total memory of (O) over tilde (m), where m is the number of edges in the graph. Notably, this is the first coloring algorithm with sublogarithmic round complexity, in the sublinear memory regime of MPC. For the quasilinear memory regime of MPC, anO(1)-round algorithm was given very recently by Assadi et al. [SODA'19].Centralized Local Computation: We show that (Delta + 1)-listcoloring can be solved by a randomized algorithm with query complexity Delta O(1) center dot O(log n), in the centralized local computation model. The previous state of the art for (Delta + 1)-list-coloring in the centralized local computation model are based on simulation of known LOCAL algorithms. The deterministic O(root Delta poly log Delta + log* n)-round LOCAL algorithm of Fraigniaud et al. [FOCS'16] can be implemented in the centralized local computation model with query complexity Delta(O(root Delta poly log) (Delta)) center dot O(log* n); the randomized Delta O(log*Delta) + 2(O(root log log n))-round LOCAL algorithm of Chang et al. [STOC'18] can be implemented in the centralized local computation model with query complexity Delta(O(log*Delta)) center dot O(log n).

在本文中，我们提出了新的随机算法，这些算法在分布式、并行和集中式计算这三个经过充分研究的模型中，改进了经典的（Δ + 1）-着色问题及其推广（Δ + 1）-列表着色问题的复杂度： 分布式拥塞团：我们提出了一种在分布式计算的拥塞团模型中用于（Δ + 1）-列表着色的O(1)轮随机算法。这确定了该问题的渐近复杂度。此外，它改进了帕尔特和苏[DISC'18]的O(log*Δ)轮随机算法以及帕尔特[ICALP'18]的O((log log.)×log*Δ)轮随机算法。 大规模并行计算：我们提出了一种在每台机器具有强次线性内存的大规模并行计算（MPC）模型中，轮复杂度为O(√log logn)的随机（Δ + 1）-列表着色算法。对于任何期望的常数α > 0，该算法每台机器使用O(n^α)的内存，并且总内存为~O(m)，其中m是图中的边数。值得注意的是，这是在MPC的次线性内存机制下第一个具有次对数轮复杂度的着色算法。对于MPC的拟线性内存机制，阿萨迪等人[SODA'19]最近给出了一种O(1)轮算法。 集中式局部计算：我们表明，在集中式局部计算模型中，（Δ + 1）-列表着色可以通过一种查询复杂度为Δ^O(1)×O(log n)的随机算法来解决。在集中式局部计算模型中，（Δ + 1）-列表着色的先前技术水平是基于对已知局部（LOCAL）算法的模拟。弗雷尼亚德等人[FOCS'16]的确定性O(√Δ poly log Δ + log*n)轮局部算法可以在集中式局部计算模型中以查询复杂度为Δ^(O(√Δ poly log Δ))×O(log*n)来实现；张等人[STOC'18]的随机Δ^O(log*Δ) + 2^(O(√log log n))轮局部算法可以在集中式局部计算模型中以查询复杂度为Δ^(O(log*Δ))×O(log n)来实现。