Constant Time Coloring in the Congested Clique

Given an undirected graph of degree D, a simple linear-time greedy algorithm guarantees that it has a (D+1)-vertex coloring. However, if one considers solving the coloring problem in the distributed setting, it becomes meaningful to optimize the complexity of the algorithm. In this talk, I will present an O(1)-time algorithm for (D+1)-vertex coloring in the CONGESTED-CLIQUE model. In order to obtain this asymptotically optimal algorithm, we exploit the existence of a fast coloring algorithm in the LOCAL model. This CONGESTED-CLIQUE algorithm, along with our results in other models, gives a good example that several distributed computing model (e.g., including LOCAL, LCA, MPC, CONGEST and CONGESTED-CLIQUE) are closely related, by demonstrating that an algorithm in one model often helps us develop an algorithm in another model.

Joint work with Yi-Jun Chang, Manuela Fischer, Mohsen Ghaffari and Jara Uitto.

Manuscript available at: https://arxiv.org/abs/1808.08419.