Simple Graph Coloring Algorithms for Congested Clique and Massively Parallel Computation.
Manuela Fischer, Mohsen Ghaffari, Jara Uitto · arXiv (Cornell University) · 2018
We present a very simple randomized partitioning procedure for graph coloring, which leads to simplification or improvements of some recent distributed and parallel coloring algorithms. In particular, we get a simple $(\Delta+1)$ coloring algorithm with round complexity $O(\log^* \Delta)$ in the CONGESTED CLIQUE model of distributed computing. This matches the bound of Parter and Su [DISC'18], which improved on the $O(\log\log \Delta \log^* \Delta)$-round algorithm of Parter [ICALP'18]. Moreover, the same random partitioning leads to a $(\Delta+1)$ coloring algorithm with round complexity $O(\log^* \Delta+ \sqrt{\log\log n})$ in the Massively Parallel Computation (MPC) model with strongly sublinear memory, which is the first sublogarithmic-time algorithm in this regime. This algorithm uses a memory of $O(n^{\alpha})$ per machine, for any desirable constant $\alpha>0$, and a total memory of $\widetilde{O}(m)$, where $m$ is the size of the graph.