Deterministic graph coloring in the streaming model

DOI10.1145/3519935.3520016arXiv2109.14891OpenAlexW3203563530MaRDI QIDQ6083483

Author name not available (Why is that?)

Publication date: 8 December 2023

Published in: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Recent breakthroughs in graph streaming have led to the design of single-pass semi-streaming algorithms for various graph coloring problems such as $(Delta+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 $Delta$, can output a proper coloring of $G$ using any number of colors which is sub-exponential in $Delta$. 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 just one extra pass over the input allows one to recover an $O(Delt{a}^2)$ coloring via a deterministic semi-streaming algorithm. This result is further extended to an $O(Delta)$ coloring in $O(logDelta)$ passes even in dynamic streams.

Full work available at URL: https://arxiv.org/abs/2109.14891

zbMATH Keywords

graph coloringdeterministic algorithmslower boundsstreaming

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring ⋮ Brooks' theorem in graph streams: a single-pass semi-streaming algorithm for \(\Delta\)-coloring

Recommendations

• On the dynamic coloring of graphs 👍 👎
• Graph coloring in linear time 👍 👎
• On graph problems in a semi-streaming model 👍 👎
• Dynamic coloring of graphs 👍 👎
• Sequential and distributed graph coloring algorithms with performance analysis in random graph spaces 👍 👎
• Streaming Algorithms for 2-Coloring Uniform Hypergraphs 👍 👎
• Automata, Languages and Programming 👍 👎
• Brooks’ theorem in graph streams: a single-pass semi-streaming algorithm for ∆-coloring 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Deterministic graph coloring in the streaming model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083483)