Distributed graph coloring: The loglog-revolution

8^th December 2022, 16:15
Magnus Halldorsson
Reykjavik University, Iceland

Abstract

The graph coloring problem is fundamental to distributed computing, as an elegant way of breaking symmetry and sharing resources. For the core problem of using $\Delta+1$ colors, where $\Delta$ is the maximum degree, a randomized algorithm of Chang, Li and Pettie [STOC’18] achieves the best complexity known of $O(\log^3 \log n)$ rounds of the LOCAL model, when combined with the recent deterministic algorithm of Ghaffari and Kuhn [FOCS’21].

We describe recent results that are simpler, faster, more general, use fewer colors, and/or are bandwidth efficient. In particular, we give a simplified framework that holds in the CONGEST model and is ultrafast when $\Delta$ is sufficiently large. We apply it to get fast algorithms for the more general degree+1-list coloring and the $\Delta$-coloring problems.

This is joint work with Manuela Fischer, Fabian Kuhn, Yannic Maus, Alexandre Nolin, and Tigran Tonoyan, appearing in STOC’21, STOC’22, SIROCCO’22, and SODA’23.