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 ∆-coloring
复制标题
DOI：
10.1145/3519935.3520005
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Pankaj Kumar;Parth Mittal
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Pankaj Kumar;Parth Mittal
每个具有最大度Δ的图都可以使用简单的贪婪算法给(Δ+1)种颜色上色。值得注意的是，最近的工作表明，即使在半流模型中也可以找到这样的着色：存在一个随机算法，该算法假设以任意顺序通过图的边一遍，则很有可能在O(n.logn)空间中找到输入图的(Δ+1)-着色。但是，在现实中，人们几乎不需要(Δ+1)种颜色来正确地给图形上色。事实上，著名的布鲁克斯定理指出，除了团和奇圈之外，每个(连通的)图都可以用Δ颜色着色。我们能在半流媒体模式中找到Δ-Colding吗？我们通过设计一种随机化的半流算法来肯定地解决了这一关键问题，该算法在给定任何图的情况下，高概率地要么正确地声明该图不是Δ可染的，要么输出该图的Δ着色。对这一结果的证明始于绕道而行。我们首先(可证明)确定了以前的流着色方法在Δ着色中的失败程度：例如，所有这些方法都可以处理具有重复边的流，并且它们可以在o(N2)时间内运行--我们证明了这些任务都不可能用于Δ着色。然而，这些不可能的结果准确地指出了以前的方法在Δ着色方面所缺少的东西。然后，我们在这些见解的基础上设计了一个半流算法，它使用(I)一种基于稀疏-密集分解的新的稀疏恢复方法来(部分)恢复输入的“有问题的”子图--这些子图构成了我们的不可能结果的基础--以及(Ii)对于这些子图的新的着色方法，它允许以受控的方式重新着色其他顶点，而不依赖于局部探索或寻找通常不可能用于半流算法的“扩充路径”。我们相信这两种技术都可能是独立的。
Every graph with maximum degree Δ can be colored with (Δ+1) colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model: there exists a randomized algorithm that with high probability finds a (Δ+1)-coloring of the input graph in only O(n·logn) space assuming a single pass over the edges of the graph in any arbitrary order. But, in reality, one almost never needs (Δ+1) colors to properly color a graph. Indeed, the celebrated Brooks’ theorem states that every (connected) graph beside cliques and odd cycles can be colored with Δ colors. Can we find a Δ-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not Δ-colorable or outputs a Δ-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for Δ-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in o(n2) time – we prove that neither of these tasks is possible for Δ-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to Δ-coloring. We then build on these insights to design a semi-streaming algorithm that uses (i) a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the ”problematic” subgraphs of the input—the ones that form the basis of our impossibility results—and (ii) a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding ”augmenting paths” that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.