Deterministic graph coloring in the streaming model

Sepehr Assadi, Andrew Chen, Glenn Sun

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

4 Scopus citations

Abstract

Recent breakthroughs in graph streaming have led to design of semi-streaming algorithms for various graph coloring problems such as ("+1)-coloring, degeneracy-coloring, coloring triangle-free graphs, and others. These algorithms are all randomized in crucial ways and whether or not there is any deterministic analogue of them has remained an important open question in this line of work. We settle this fundamental question by proving that there is no deterministic single-pass semi-streaming algorithm that given a graph G with maximum degree ", can output a proper coloring of G using any number of colors which is sub-exponential in ". Our proof is based on analyzing the multi-party communication complexity of a related communication game, using random graph theory type arguments that may be of independent interest. We complement our lower bound by showing that one extra pass over the input allows one to recover an O("2) coloring via a deterministic semi-streaming algorithm. This result is extended to an O(") coloring in O(log") passes even in dynamic streams.

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
Pages261-274
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

  • Graph coloring
  • deterministic algorithms
  • lower bounds
  • streaming

Fingerprint

Dive into the research topics of 'Deterministic graph coloring in the streaming model'. Together they form a unique fingerprint.

Cite this