论文标题
通过确定性和对抗性鲁棒算法在图流中着色
Coloring in Graph Streams via Deterministic and Adversarially Robust Algorithms
论文作者
论文摘要
近年来，人们对在流模型中解决各种图形着色问题的兴趣越来越大。这项工作中的初始算法都是至关重要的随机性的，这引发了关于随机在流式图上扮演的重要性的自然问题。最近的几部作品在这个问题上取得了进展：他们证明确定性甚至对抗性强大的着色算法（在其更新可能取决于该算法的过去输出的流中的作品）比标准随机分析的算法要弱得多。但是，对于鲁棒着色和多种确定性着色所需的颜色数量（作为最大程度$δ$的函数），上限和下限之间仍然存在显着差距。我们通过证明以下结果来为这项工作做出贡献。 在确定性的半流（即$ o（n \ cdot \ text {polylog} n）$ space）方案中，我们提出了一种算法，该算法可实现组合上最佳$（δ+1）$ - 使用$ o（\ loguex \ logu \ log \ log \logΔ）$ Passes的颜色。这可以改善Assadi，Chen和Sun（STOC 2022）的先前的$ O（δ）$ - 着色算法，仅为$ o（\ log \ logudugention）$（\ log \logδ）$ factor。 在对抗性稳健的半流式方案中，我们设计了一个$ O（δ^{5/2}）$ - 着色算法，该算法可以改善以前最佳的$ o（δ^{3}）$ - chakrabarti，ghosh，ghosh和stoeckl（Itcs 2022222）的chakrabarti，ghosh，ghosh，ghosh，ghosh，ghosh，ghosh，ghosh，ghosh和stoeckl algorithm。此外，我们获得了上述工作的另一种算法的光滑色彩/空间折衷，而他们的算法使用$ o（δ^2）$ colors和$ o（nδ^{1/2}）$ space，我们的Space，尤其是Achieves（i）〜$ O（δ^2）$（δ^2）$（δ^2）$（Δ^2）$（Δ^2） （ii）〜$ o（δ^{7/4}）$ o（nδ^{1/2}）$ space中的$ colors。
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 have made progress on this question: they 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 \cdot \text{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.
