Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration
复制标题
改进的分布式扩展器分解和近乎最优的三角形枚举
DOI：
10.1145/3293611.3331618
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Saranurak, Thatchaphol
中科院分区：
文献类型：
--
作者：
Chang, Yi-Jun;Saranurak, Thatchaphol
图G=（V，E）的一个（ε，φ）-扩展分解是顶点V=V1的一个聚类，使得（1）每个聚类Vi诱导的子图的电导至少为φ，（2）聚类间的边数至多为ε| E|.本文给出了一种改进的分布式扩展分解，并在CONGEST模型下得到了一个近似最优的分布式三角形枚举算法，具体地说，对于任意的ε ∈（0，1）和正整数k，我们构造了一个（ε，φ）-扩展分解，其中φ=（ε/logn）2 O（k），循环次数为O（n2/k poly（1/φ，logn））.例如，（1/no（1），1/no（1））-扩展器分解只需要O（no（1））轮来计算，这对于子多项式因子是最优的，并且对于任何任意小的常数γ > 0，（0.01，1/poly log n）-扩展器分解可以在O（nγ）轮中计算。以前，Chang，Pettie和Zhang的算法可以对任何δ > 0使用n（n1-δ）轮来构造（1/6，1/poly log n）-扩展器分解，但需要注意的是，该算法允许将一组边丢弃到形成荫度至多为nδ的子图的额外部分中。通过对Ghaffari，Kuhn和Su [PODC'17]提出的扩展器上的分布式路由算法稍加修改，我们得到了一个使用n（n1/3）轮的三角枚举算法。这与Izumi和LeGall [PODC'17]以及Pandurangan，罗宾逊和Scquizzato [SPAA'18]的下限（n1/3）相匹配，即使在CONGESTED-CLIQUE模型中也是如此。据我们所知，这提供了第一个非平凡的例子，一个分布式的问题，具有基本上相同的复杂性（多对数因子）在CONGEST和CONGESTED-CLIQUE。在我们的证明中的关键技术是第一个分布式近似算法，找到一个低电导切割，是尽可能平衡。以前的分布式稀疏切割算法没有这种几乎最平衡的保证。
An(ε,φ)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V1∪…∪ Vxsuch that (1) each cluster Viinduces subgraph with conductance at least φ, and (2) the number of inter-cluster edges is at most ε|E|. In this paper, we give an improved distributed expander decomposition, and obtain a nearly optimal distributed triangle enumeration algorithm in the CONGEST model.Specifically, we construct an (ε,φ)-expander decomposition with φ=(ε/log n)2 O(k)in O(n2/k⋅ poly (1/φ, log n))rounds for any ε ∈(0,1) and positive integer k. For example, a (1/no(1), 1/no(1))-expander decomposition only requires O(no(1)) rounds to compute, which is optimal up to subpolynomial factors, and a (0.01,1/poly log n)-expander decomposition can be computed in O(nγ) rounds, for any arbitrarily small constant γ > 0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1/6,1/poly log n)-expander decomposition using Õ (n1-δ) rounds for any δ > 0, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which form a subgraph with arboricity at most nδ. Our algorithm does not have this caveat.By slightly modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC'17], we obtain a triangle enumeration algorithm using Õ(n1/3) rounds. This matches the lower bound by Izumi and LeGall [PODC'17] and Pandurangan, Robinson and Scquizzato [SPAA'18] of Ø(n1/3) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a distributed problem that has essentially the same complexity (up to a polylogarithmic factor) in both CONGEST and CONGESTED-CLIQUE.The key technique in our proof is the first distributed approximation algorithm for finding a low conductance cut that is as balanced as possible. Previous distributed sparse cut algorithms do not have this nearly most balanced guarantee.
登录
查看更多内容
拥塞团模型中的稀疏矩阵乘法和三角形列表
DOI：
--
发表时间：
2018
期刊：
International Conference on Principles of Distributed Systems
影响因子：
--
作者：
K. Censor;Dean Leitersdorf;Elia Turner
通讯作者：
Elia Turner
具有次多项式最坏情况更新时间的动态最小生成森林
DOI：
10.1109/focs.2017.92
发表时间：
2017
期刊：
2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS)
影响因子：
--
作者：
Danupon Nanongkai;Thatchaphol Saranurak;Christian Wulff
通讯作者：
Christian Wulff
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
分布式子图检测的可能性和不可能性
DOI：
--
发表时间：
2018
期刊：
ACM Symposium on Parallelism in Algorithms and Architectures
影响因子：
--
作者：
O. Fischer;T. Gonen;F. Kuhn;R. Oshman
通讯作者：
R. Oshman
DOI：
10.1145/3087801.3087827
发表时间：
2017-07
期刊：
Proceedings of the ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su
通讯作者：
M. Ghaffari;F. Kuhn;Hsin-Hao Su