Treffer: SIMPLE, DETERMINISTIC, CONSTANT-ROUND COLORING IN CONGESTED CLIQUE AND MPC.

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. [Proceedings of the 38th ACM Symposium on Principles of Distributed Computing, 2019] and significantly improves upon the state-of-the-art O(log)-round deterministic (Δ + 1)-coloring bound of Parter [Proceedings of the 45th Annual International Colloquium on Automata, Languages and Programming]. 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, Li, and Pettie [Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018], 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. [ABSTRACT FROM AUTHOR]

Copyright of SIAM Journal on Computing is the property of Society for Industrial & Applied Mathematics and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)