Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
Graph Coloring via Degeneracy in Streaming and Other Space-Conscious Models
复制标题
DOI：
10.4230/lipics.icalp.2020.11
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
Suman Kalyan Bera;Amit Chakrabarti;Prantar Ghosh
中科院分区：
文献类型：
--
作者：
Suman Kalyan Bera;Amit Chakrabarti;Prantar Ghosh
在几个成熟的大数据计算模型中，我们研究了使用少量颜色给给定的图着色的问题。这些模型包括数据流模型、通用图查询模型、大规模并行计算(MPC)模型、分布式计算的拥挤团模型和局部模型。一方面，我们给出了每个模型的次线性复杂度的算法，并给出了相应的复杂度概念。我们的算法使用大约$\kappa(G)$颜色给图$G$上色，其中$\kappa(G)$是$G$的简并度：这个参数与丛度$\α(G)$密切相关。仅作为$\kappa(G)$的函数，我们的结果接近最佳，因为最佳颜色数为$\kappa(G)+1$。另一方面，我们建立了一定的下界，表明次线性算法可能不会走得更远。特别地，我们证明了任何使用$\kappa(G)+1$多个颜色的随机着色算法在单遍流模型中需要$\Omega(n^2)$存储，在一般图查询模型中需要$\Omega(n^2)$次查询，其中$n$是图中的顶点数。即使在$kappa(G)$的值已知的情况下，这些下界仍然成立；同时，我们的上界不需要预先给出$kappa(G)$。
We study the problem of coloring a given graph using a small number of colors in several well-established models of computation for big data. These include the data streaming model, the general graph query model, the massively parallel computation (MPC) model, and the CONGESTED-CLIQUE and the LOCAL models of distributed computation. On the one hand, we give algorithms with sublinear complexity, for the appropriate notion of complexity in each of these models. Our algorithms color a graph $G$ using about $\kappa(G)$ colors, where $\kappa(G)$ is the degeneracy of $G$: this parameter is closely related to the arboricity $\alpha(G)$. As a function of $\kappa(G)$ alone, our results are close to best possible, since the optimal number of colors is $\kappa(G)+1$. On the other hand, we establish certain lower bounds indicating that sublinear algorithms probably cannot go much further. In particular, we prove that any randomized coloring algorithm that uses $\kappa(G)+1$ many colors, would require $\Omega(n^2)$ storage in the one pass streaming model, and $\Omega(n^2)$ many queries in the general graph query model, where $n$ is the number of vertices in the graph. These lower bounds hold even when the value of $\kappa(G)$ is known in advance; at the same time, our upper bounds do not require $\kappa(G)$ to be given in advance.