Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for †-coloring

Sepehr Assadi, Pankaj Kumar, Parth Mittal

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

Every graph with maximum degree Δcan be colored with ("+1) colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model: there exists a randomized algorithm that with high probability finds a ("+1)-coloring of the input graph in only O(n·logn) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs ("+1) colors to properly color 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 the extent to which the previous approaches for streaming coloring fail for "-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in o(n2) time-we prove that neither of these tasks is possible 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 "problematic"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.

Original languageEnglish (US)
Title of host publicationSTOC 2022 - Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing
EditorsStefano Leonardi, Anupam Gupta
PublisherAssociation for Computing Machinery
Pages234-247
Number of pages14
ISBN (Electronic)9781450392648
DOIs
StatePublished - Sep 6 2022
Event54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022 - Rome, Italy
Duration: Jun 20 2022Jun 24 2022

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference54th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2022
Country/TerritoryItaly
CityRome
Period6/20/226/24/22

All Science Journal Classification (ASJC) codes

  • Software

Keywords

  • brooks' theorem
  • graph coloring
  • streaming algorithms

Fingerprint

Dive into the research topics of 'Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for †-coloring'. Together they form a unique fingerprint.

Cite this