Adversarially Robust Coloring for Graph Streams-猫眼课题宝

DOI：

10.4230/lipics.itcs.2022.37

发表时间：

2021-09

期刊：

ArXiv

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

Amit Chakrabarti;Prantar Ghosh;Manuel Stoeckl

如果流算法提供具有高概率的正确输出，即使当流更新由可能观察算法的过去输出并对其作出反应的对手选择时，也认为该流算法是对抗性鲁棒的。我们成长的新兴机构的工作，这样的算法在一个新的方向，通过研究强大的算法，保持一个有效的顶点着色的一个$n$-顶点图流的边缘的问题。按照标准的做法，我们专注于最大度最多为$\Delta$的图，目标是使用少量的$f（\Delta）$颜色进行着色。最近的一项突破（Assadi，Chen和卡纳; SODA~2019）表明，在标准的非鲁棒流设置中，可以在仅使用$\widetilde{O}（n）$空间的情况下获得$（\Delta+1）$-着色。在这里，我们证明了一个adversarially鲁棒算法运行在一个类似的空间界限必须花费几乎$\Omega（\Delta^2）$的颜色和强大的$O（\Delta）$-着色需要一个线性量的空间，即$\Omega（n\Delta）$。事实上，我们得到了一个更一般的下限，权衡了空间使用对颜色使用的数量。从复杂性理论的角度来看，这些下界提供了（i）对抗性鲁棒算法和普通随机算法之间的第一个显着分离，用于仅插入流上的自然问题，以及（ii）随机和确定性着色算法之间的第一个显着分离，用于图形流，因为确定性流算法是自动鲁棒的。我们补充我们的下界与一套积极的结果，给adversarially强大的着色算法，使用次线性空间。特别地，我们可以使用$\widetilde{O}（n \sqrt{\Delta}）$空间保持$O（\Delta^2）$-着色，使用$\widetilde{O}（n）$空间保持$O（\Delta^3）$-着色。

A streaming algorithm is considered to be adversarially robust if it provides correct outputs with high probability even when the stream updates are chosen by an adversary who may observe and react to the past outputs of the algorithm. We grow the burgeoning body of work on such algorithms in a new direction by studying robust algorithms for the problem of maintaining a valid vertex coloring of an $n$-vertex graph given as a stream of edges. Following standard practice, we focus on graphs with maximum degree at most $\Delta$ and aim for colorings using a small number $f(\Delta)$ of colors. A recent breakthrough (Assadi, Chen, and Khanna; SODA~2019) shows that in the standard, non-robust, streaming setting, $(\Delta+1)$-colorings can be obtained while using only $\widetilde{O}(n)$ space. Here, we prove that an adversarially robust algorithm running under a similar space bound must spend almost $\Omega(\Delta^2)$ colors and that robust $O(\Delta)$-coloring requires a linear amount of space, namely $\Omega(n\Delta)$. We in fact obtain a more general lower bound, trading off the space usage against the number of colors used. From a complexity-theoretic standpoint, these lower bounds provide (i)~the first significant separation between adversarially robust algorithms and ordinary randomized algorithms for a natural problem on insertion-only streams and (ii)~the first significant separation between randomized and deterministic coloring algorithms for graph streams, since deterministic streaming algorithms are automatically robust. We complement our lower bounds with a suite of positive results, giving adversarially robust coloring algorithms using sublinear space. In particular, we can maintain an $O(\Delta^2)$-coloring using $\widetilde{O}(n \sqrt{\Delta})$ space and an $O(\Delta^3)$-coloring using $\widetilde{O}(n)$ space.

Adversarially Robust Coloring for Graph Streams

文献摘要

相似文献