The Complexity of Symmetry Breaking in Massive Graphs
The Complexity of Symmetry Breaking in Massive Graphs
复制标题
海量图中对称性破缺的复杂性
DOI：
10.4230/lipics.disc.2019.26
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Peter Robinson
中科院分区：
文献类型：
--
作者：
C. Konrad;Sriram V. Pemmaraju;Talal Riaz;Peter Robinson
本文的目标是了解对称性破缺问题的复杂性，特别是最大独立集（MIS）和密切相关的$\beta$-规则集问题，在两个计算模型适合于大规模的图形处理，即$k$-机模型和图形流模型。我们提出了一些结果。对于$k$-机器模型中的MIS，我们通过提出$\tilde {O}（m/k^2）$-轮算法改进了Klauck等人（SODA 2015）的$\tilde {O}（m/k^2 + \Delta/k）$-轮上界。我们还提出了一个$\tilde{\Omega}（n/k^2）$轮下限MIS，第一个下界的对称性破缺问题的$k$-机模型。对于$\beta$-规则集，我们使用分层抽样，以获得更有效的算法在$k$-机模型，也在图流模型。更具体地说，我们得到了一个运行在$\tilde{O}（\beta n\Delta^{1/\beta}/k^2）$轮中的$k$机器算法，并且通过使用类似的分层采样技术，我们得到了使用$O（\beta \cdot n^{1+1/2^{\beta-1}}）$空间的仅插入流和插入删除流的一次通过算法。后一个结果在MIS之间建立了明确的分离，已知MIS需要$\Omega（n^2）$空间（Cormode等人，ICALP 2019）和$\beta$-规则集，即使对于$\beta = 2$。最后，我们提出了一个更快的2-规则集算法在$k$-机器模型，一个运行在$\tilde{O}（n/k^{2-\times} + k^{1-\times}）$轮为任何$\times $，$0 \le \times\le 1$。
The goal of this paper is to understand the complexity of symmetry breaking problems, specifically maximal independent set (MIS) and the closely related $\beta$-ruling set problem, in two computational models suited for large-scale graph processing, namely the $k$-machine model and the graph streaming model. We present a number of results. For MIS in the $k$-machine model, we improve the $\tilde{O}(m/k^2 + \Delta/k)$-round upper bound of Klauck et al. (SODA 2015) by presenting an $\tilde{O}(m/k^2)$-round algorithm. We also present an $\tilde{\Omega}(n/k^2)$ round lower bound for MIS, the first lower bound for a symmetry breaking problem in the $k$-machine model. For $\beta$-ruling sets, we use hierarchical sampling to obtain more efficient algorithms in the $k$-machine model and also in the graph streaming model. More specifically, we obtain a $k$-machine algorithm that runs in $\tilde{O}(\beta n\Delta^{1/\beta}/k^2)$ rounds and, by using a similar hierarchical sampling technique, we obtain one-pass algorithms for both insertion-only and insertion-deletion streams that use $O(\beta \cdot n^{1+1/2^{\beta-1}})$ space. The latter result establishes a clear separation between MIS, which is known to require $\Omega(n^2)$ space (Cormode et al., ICALP 2019), and $\beta$-ruling sets, even for $\beta = 2$. Finally, we present an even faster 2-ruling set algorithm in the $k$-machine model, one that runs in $\tilde{O}(n/k^{2-\epsilon} + k^{1-\epsilon})$ rounds for any $\epsilon$, $0 \le \epsilon \le 1$.
DOI：
10.1145/3210377.3210409
发表时间：
2016-02
期刊：
Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
通讯作者：
Gopal Pandurangan;Peter Robinson;Michele Scquizzato
使用抽象 MAC 层分解广播算法
DOI：
10.1145/1860684.1860690
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Khabbazian M
通讯作者：
Khabbazian M