$(\Delta +1)$ Coloring in the Congested Clique Model

Abstract

In this paper, we present improved algorithms for the $(\Delta +1)$ (vertex) coloring problem in the Congested-Clique model of distributed computing. In this model, the input is a graph on $n$ nodes, initially each node knows only its incident edges, and per round each two nodes can exchange $O(\log n)$ bits of information. Our key result is a randomized $(\Delta +1)$ vertex coloring algorithm that works in $O(\log \log \Delta \cdot {\log }^{\ast }\Delta )$-rounds. This is achieved by combining the recent breakthrough result of [Chang-Li-Pettie, STOC'18] in the \local\ model and a degree reduction technique. We also get the following results with high probability: (1) $(\Delta +1)$-coloring for $\Delta =O((n/\log n{)}^{1-\epsilon })$ for any $\epsilon \in (0,1)$, within $O(\log (1/\epsilon ){\log }^{\ast }\Delta )$ rounds, and (2) $(\Delta +{\Delta }^{1/2+o(1)})$-coloring within $O({\log }^{\ast }\Delta )$ rounds. Turning to deterministic algorithms, we show a $(\Delta +1)$-coloring algorithm that works in $O(\log \Delta )$ rounds.

Appeared in ICALP'18 (the update version adds a missing part in the deterministic coloring procedure)

Cited by in corpus (1)

• Distributed MST: A Smoothed Analysis