Deterministic graph coloring in the streaming model
Deterministic graph coloring in the streaming model
复制标题
DOI：
10.1145/3519935.3520016
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Andrew Chen;Glenn Sun
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Andrew Chen;Glenn Sun
最近在图流方面的突破导致了各种图着色问题的半流算法的设计，例如（Δ+1）-着色，退化着色，无三角形图着色等。这些算法都是随机的关键方式，是否有任何确定性的类似物，他们仍然是一个重要的悬而未决的问题，在这方面的工作。我们通过证明不存在确定性的单遍半流算法来解决这个基本问题，即给定具有最大度Δ的图G，可以使用在Δ中次指数的任何数量的颜色输出G的适当着色。我们的证明是基于分析相关的通信游戏的多方通信的复杂性，使用随机图论类型的参数，可能是独立的利益。我们补充我们的下界，通过显示输入上的一个额外的通道允许通过确定性半流算法恢复O（Δ2）着色。这个结果被扩展到O（logΔ）遍数的O（Δ）着色，即使是在动态流中。
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.