论文标题
在拥挤的集团中简单，确定性，恒定的着色
Simple, Deterministic, Constant-Round Coloring in the Congested Clique
论文作者
论文摘要
我们通过在恒定数量的回合数量中提出一个简单的确定性算法，解决了拥挤集团模型中$（δ+1）$ - 着色和$（δ+1）$ - 列出着色问题的复杂性。这与最近突破性的随机恒定$（δ+1）$ - 列表着色算法的复杂性相匹配。 （PODC'19），并且在最先进的$ O（\logΔ）$ - 圆形确定性$（δ+1）$ - 颜色的颜色（ICALP'18）上显着改善。 我们的算法的非凡属性是它的简单性。而对于此问题的最新随机算法是基于Chang等人的局部着色算法。 （stoc'18），我们的算法只能用几行描述。在高水平上，它仔细地对递归程序进行了仔细的扩散，该过程将节点及其各自的调色板划分为单独的垃圾箱。我们表明，在$ O（1）$递归步骤之后，每个垃圾箱内的其余未颜色子图具有线性尺寸，因此可以通过将其收集到单个节点来本地解决。该算法也可以在大规模并行计算（MPC）模型中实现，前提是每台机器具有线性（以$ n $，输入图中的节点）空间的数量。 我们还显示了算法扩展到MPC机制，在该算法中，机器具有子宫性空间：我们介绍了为Sublinear Space MPC设计的第一个确定性$（δ+ 1）$ - 列表着色算法，该算法在$ o（\ loglogδ+δ+ \ log \ log \ log \ log \ f n）$ founds中运行。
We settle the complexity of the $(Δ+1)$-coloring and $(Δ+1)$-list coloring problems in the CONGESTED CLIQUE model by presenting a simple deterministic algorithm for both problems running in a constant number of rounds. This matches the complexity of the recent breakthrough randomized constant-round $(Δ+1)$-list coloring algorithm due to Chang et al. (PODC'19), and significantly improves upon the state-of-the-art $O(\log Δ)$-round deterministic $(Δ+1)$-coloring bound of Parter (ICALP'18). A remarkable property of our algorithm is its simplicity. Whereas the state-of-the-art randomized algorithms for this problem are based on the quite involved local coloring algorithm of Chang et al. (STOC'18), our algorithm can be described in just a few lines. At a high level, it applies a careful derandomization of a recursive procedure which partitions the nodes and their respective palettes into separate bins. We show that after $O(1)$ recursion steps, the remaining uncolored subgraph within each bin has linear size, and thus can be solved locally by collecting it to a single node. This algorithm can also be implemented in the Massively Parallel Computation (MPC) model provided that each machine has linear (in $n$, the number of nodes in the input graph) space. We also show an extension of our algorithm to the MPC regime in which machines have sublinear space: we present the first deterministic $(Δ+1)$-list coloring algorithm designed for sublinear-space MPC, which runs in $O(\log Δ+ \log\log n)$ rounds.
