论文标题
Brooks的图表中的定理：$δ$颜色的单通道半流算法
Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $Δ$-Coloring
论文作者
论文摘要
每个具有最高度$δ$的图表都可以使用简单的贪婪算法用$（δ+1）$颜色颜色。值得注意的是，最近的工作表明，即使在半流模型中，人们也可以找到这种着色。但是，实际上，几乎不需要$（δ+1）$颜色才能正确颜色图形。的确，著名的\ brooks的定理指出，在集团和奇数周期旁边的每个（连接）图都可以用$Δ$颜色颜色。我们还能在半流模型中找到$δ$颜色吗？ 我们通过设计一种随机的半流算法来解决这个关键问题，该算法具有任何图形，具有很高的概率，可以正确地声明该图不是$δ$ - 可溶剂，或者输出图形的$δ$ - 颜色。 此结果的证明始于绕道。我们首先（证明是）确定以前流式着色方法以$δ$ - 颜色的方式失败的程度：例如，所有这些方法都可以用重复的边缘处理流，并且它们可以以$ O（n^2）$时间运行 - 我们证明这些任务都不是$δ$颜色的。但是，这些不可能的结果确切地指出了$δ$颜色时先前方法所缺少的内容。 然后，我们基于这些见解，以设计一种半流的算法，该算法使用$（i）$基于稀疏浓度分解的新型稀疏回收方法，以（部分）恢复（部分）恢复输入的“有问题”子图的“有问题的”子图，而这些算法构成了我们不可能的结果的基础，而这些方法是允许这些供您进行的新颜色的方法，并且是$（ii）$（ii）$（ii）$（ii）$（ii）的范围，该方法是在$（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. 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(n^2)$ 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.
