Brooks’ Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for ∆-Coloring
Authors:
Sepehr Assadi, Pankaj Kumar, Parth Mittal.
Abstract:
Every graph with maximum degree ∆ can be colored with (∆ + 1) colors using a simple greedy algorithm. Remarkably, recent work have shown that one can find such a coloring even in the semi-streaming model: there exist a randomized algorithm that with high probability finds a (∆ + 1)-coloring of the input graph in only O(n · polylog n) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs (∆ + 1) colors for proper coloring a graph. Indeed, the celebrated Brooks’ theorem states that every (connected) graph beside cliques and odd cycles can be colored with ∆ colors. Can we find a ∆-coloring in the semi-streaming model as well?
We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not ∆-colorable or outputs a ∆-coloring of the graph.
The proof of this result starts with a detour. We first (provably) identify to what extent the previous approaches for streaming coloring fail for ∆-coloring: for instance, all these approaches naturally handle streams with repeated edges and they can also run in o(n2) time – we prove that either of these tasks are simply impossible for ∆-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to ∆-coloring.
We then build on these insights to design a semi-streaming algorithm that uses (i) a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the “prob- lematic” subgraphs of the input—the ones that form the basis of our impossibility results—and (ii) a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding “augmenting paths” that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not ∆-colorable or outputs a ∆-coloring of the graph.
The proof of this result starts with a detour. We first (provably) identify to what extent the previous approaches for streaming coloring fail for ∆-coloring: for instance, all these approaches naturally handle streams with repeated edges and they can also run in o(n2) time – we prove that either of these tasks are simply impossible for ∆-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to ∆-coloring.
We then build on these insights to design a semi-streaming algorithm that uses (i) a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the “prob- lematic” subgraphs of the input—the ones that form the basis of our impossibility results—and (ii) a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding “augmenting paths” that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.
Conference version:
[PDF]
Full version:
[arXiv]
Streaming video:
[YouTube] (Parth @STOC'22)
BibTex:
[DBLP]