Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
复制标题
DOI：
10.1145/3584372.3588681
复制
发表时间：
2022-12
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Amit Chakrabarti;Prantar Ghosh;Manuel Stoeckl
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Amit Chakrabarti;Prantar Ghosh;Manuel Stoeckl
图着色是一个基本问题，在包括数据挖掘和数据库在内的各个领域都有广泛的应用，例如并行查询优化。近年来，人们对解决流模型中的各种图着色问题越来越感兴趣。这一行的初始算法都是非常随机的，这就自然而然地提出了一个问题：随机化在流式图着色中扮演了多么重要的角色。最近的一些研究证明，确定性甚至对抗鲁棒的着色算法（适用于其更新可能依赖于算法过去的输出的流）比标准的随机化算法弱得多。然而，对于鲁棒着色和多通道确定性着色，所需的颜色数量（作为最大程度Δ的函数）的上界和下界之间仍然存在显着差距。我们通过证明以下结果为这一工作做出了贡献。在确定性半流（即O（n·polylog n）空间）中，我们提出了一种使用O（logΔ log logΔ）通道实现组合最优（Δ+1）着色的算法。这在Assadi， Chen和Sun （STOC 2022）之前的O（Δ）着色算法的基础上进行了改进，其代价仅是通过次数的O（log logΔ）因子。在对抗鲁棒半流机制中，我们设计了一种O（Δ5/2）-着色算法，该算法改进了Chakrabarti， Ghosh和Stoeckl （ITCS 2022）先前最佳的O（Δ3）-着色算法。此外，我们获得了平滑的颜色/空间权衡，改进了上述工作的另一种算法：而他们的算法使用O（Δ2）颜色和O（nΔ1/2）空间，特别是我们的算法，在O（nΔ1/3）空间中实现了(i)~O（Δ2）颜色，在O（nΔ1/2）空间中实现了（ii）~O（Δ7/4）颜色。
Graph coloring is a fundamental problem with wide reaching applications in various areas including ata mining and databases, e.g., in parallel query optimization. In recent years, there has been a growing interest in solving various graph coloring problems in the streaming model. The initial algorithms in this line of work are all crucially randomized, raising natural questions about how important a role randomization plays in streaming graph coloring. A couple of very recent works prove that deterministic or even adversarially robust coloring algorithms (that work on streams whose updates may depend on the algorithm's past outputs) are considerably weaker than standard randomized ones. However, there is still a significant gap between the upper and lower bounds for the number of colors needed (as a function of the maximum degree Δ) for robust coloring and multipass deterministic coloring. We contribute to this line of work by proving the following results. In the deterministic semi-streaming (i.e., O(n · polylog n) space) regime, we present an algorithm that achieves a combinatorially optimal (Δ+1)-coloring using O(logΔ log logΔ) passes. This improves upon the prior O(Δ)-coloring algorithm of Assadi, Chen, and Sun (STOC 2022) at the cost of only an O(log logΔ) factor in the number of passes. In the adversarially robust semi-streaming regime, we design an O(Δ5/2)-coloring algorithm that improves upon the previously best O(Δ3)-coloring algorithm of Chakrabarti, Ghosh, and Stoeckl (ITCS 2022). Further, we obtain a smooth colors/space tradeoff that improves upon another algorithm of the said work: whereas their algorithm uses O(Δ2) colors and O(nΔ1/2) space, ours, in particular, achieves (i)~O(Δ2) colors in O(nΔ1/3) space, and (ii)~O(Δ7/4) colors in O(nΔ1/2) space.