Theory Seminar - Sublinear Algorithms for (Delta+1) Vertex Coloring

Sublinear Algorithms for (Delta+1) Vertex Coloring

Abstract: In this talk, we will examine a classical graph coloring problem through the lens of sublinear algorithms—these are algorithms that use computational resources that are substantially smaller than the size of the input on which they operate. It is well-known that any graph with maximum degree Delta admits a proper vertex coloring with (Delta + 1) colors that can be found via a simple sequential greedy algorithm in linear time and space. But can one find such a coloring via a sublinear algorithm? We will present results that answer this question in the affirmative for several well-studied models of sublinear computation, most notably graph streaming and sublinear time algorithms. We obtain these results by proving a palette sparsification theorem which says that if every vertex independently samples O(log n) colors from the available Delta+1 colors, then almost certainly a (Delta + 1) coloring can be found using only the sampled colors. We then show that this palette sparsification theorem naturally leads to essentially optimal sublinear algorithms in each of the above-mentioned models of computation.

Based on joint work with Yu Chen and Sanjeev Khanna.