Jaehyun Koo (구재현), Dynamic Graph Coloring: Sequential, Parallel, and Distributed

For any graph with maximum degree at most $\Delta$, a simple inductive argument shows that the graph can be properly colored using $\Delta+1$ colors. However, a direct implementation of this argument is highly sequential, motivating extensive research into efficient algorithms in parallel, distributed, and dynamic settings.

In this talk, I will present a simple randomized algorithm that efficiently maintains a $(\Delta+1)$-coloring under edge insertions and deletions. Despite its remarkably simple implementation, the algorithm requires a subtle analysis due to its heavy use of randomization. I will also discuss prior and related work on the development of highly efficient $(\Delta+1)$-coloring algorithms.

A key advantage of this algorithm is its ability to process many updates simultaneously, which makes it naturally adaptable to parallel and distributed computations. In the sequential setting, the algorithm processes each update in $O(1)$ expected time, worst-case. More importantly, the algorithm admits a natural implementation in both parallel setting and the distributed CONGEST setting, with $O(1)$ expected work and message per update in a batch in $poly(\log n)$ depth and round with high probability. This is, in a sense, an ideal parallelization of the above results.

The talk is based on the joint work with Mohsen Ghaffari (MIT).