Sublinear Algorithms for (∆ + 1) Vertex Coloring
Authors:
Sepehr Assadi, Yu Chen, Sanjeev Khanna.
Conference:
The 30th ACM-SIAM Symposium on Discrete Algorithms (SODA'19)
Recipient of the Best Paper Award at SODA 2019.
Abstract:
Any graph with maximum degree ∆ admits a proper vertex coloring with ∆+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 answer this fundamental question in the affirmative for several canonical classes of sublinear al- gorithms including graph streaming, sublinear time, and massively parallel computation (MPC) algorithms.
In particular, we design:
• A single-pass semi-streaming algorithm in dynamic streams using tilde{O}(n) space. The only known semi-streaming algorithm prior to our work was a folklore O(log n)-pass algorithm obtained by simulating classical
distributed algorithms in the streaming model.
• A sublinear-time algorithm in the standard query model that allows neighbor queries and pair queries using tilde{O}(n√n) time. We further show that any algorithm that outputs a valid coloring with
sufficiently large constant probability requires Ω(n√n) time. No non-trivial sublinear time algorithms were known prior to our work.
• A parallel algorithm in the massively parallel computation (MPC) model using tilde{O}(n) memory per machine and O(1) MPC rounds. Our number of rounds significantly improves upon the recent O(log log ∆ · log∗(n))-round algorithm of Parter [ICALP 2018].
At the core of our results is a remarkably simple meta-algorithm for the (∆ + 1) coloring problem: Sample O(log n) colors for each vertex independently and uniformly at random from the ∆ + 1 colors; find a proper coloring of the graph using only the sampled colors of each vertex. As our main result, we prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in each model.
We note that all our upper bound results for (∆ + 1) coloring are either optimal or close to best possible in each model studied. We also establish new lower bounds that rule out the possibility of achieving similar results in these models for the closely related problems of maximal independent set and maximal matching. Collectively, our results highlight a sharp contrast between the complexity of (∆+1) coloring vs maximal independent set and maximal matching in various models of sublinear computation even though all three problems are solvable by a simple greedy algorithm in the classical setting.
• A parallel algorithm in the massively parallel computation (MPC) model using tilde{O}(n) memory per machine and O(1) MPC rounds. Our number of rounds significantly improves upon the recent O(log log ∆ · log∗(n))-round algorithm of Parter [ICALP 2018].
At the core of our results is a remarkably simple meta-algorithm for the (∆ + 1) coloring problem: Sample O(log n) colors for each vertex independently and uniformly at random from the ∆ + 1 colors; find a proper coloring of the graph using only the sampled colors of each vertex. As our main result, we prove that the sampled set of colors with high probability contains a proper coloring of the input graph. The sublinear algorithms are then obtained by designing efficient algorithms for finding a proper coloring of the graph from the sampled colors in each model.
We note that all our upper bound results for (∆ + 1) coloring are either optimal or close to best possible in each model studied. We also establish new lower bounds that rule out the possibility of achieving similar results in these models for the closely related problems of maximal independent set and maximal matching. Collectively, our results highlight a sharp contrast between the complexity of (∆+1) coloring vs maximal independent set and maximal matching in various models of sublinear computation even though all three problems are solvable by a simple greedy algorithm in the classical setting.
Conference version:
[PDF]
Full version:
[arXiv]
Streaming video:
[YouTube1] (Simons workshop on sublinear algorithms)
-- [YouTube2] (Highlights of Algorithms (HALG 2020))
Presentation slides:
[PDF]
Lecture notes:
[PDF] (containing a streamlined proof of the meta-algorithm)
Blog post:
[Property Testing Review]
BibTex:
[DBLP]