Near-optimal Distributed Triangle Enumeration via Expander Decompositions
Near-optimal Distributed Triangle Enumeration via Expander Decompositions
复制标题
通过扩展器分解进行近乎最优的分布式三角形枚举
DOI：
10.1145/3446330
复制
发表时间：
2021
影响因子：
2.5
通讯作者：
Zhang, Hengjie
中科院分区：
文献类型：
--
作者：
Chang, Yi-Jun;Pettie, Seth;Saranurak, Thatchaphol;Zhang, Hengjie
We present improved distributed algorithms for variants of the triangle finding problem in the <?TeX $\mathsf {CONGEST}$?> model. We show that triangle detection, counting, and enumeration can be solved in <?TeX $\tilde{O}(n^{1/3})$?> rounds usingexpander decompositions. This matches the triangle enumeration lower bound of <?TeX $\tilde{\Omega }(n^{1/3})$?> by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the <?TeX $\mathsf {CONGESTED}\text{-}\mathsf {CLIQUE}$?> model. The previous upper bounds for triangle detection and enumeration in <?TeX $\mathsf {CONGEST}$?> were <?TeX $\tilde{O}(n^{2/3})$?> and <?TeX $\tilde{O}(n^{3/4})$?>, respectively, due to Izumi and Le Gall [PODC’17].An <?TeX $(\epsilon ,\phi)$?>-expander decomposition of a graph <?TeX $G=(V,E)$?> is a clustering of the vertices <?TeX $V=V_{1}\cup \cdots \cup V_{x}$?> such that (i) each cluster <?TeX $V_{i}$?> induces a subgraph with conductance at least <?TeX $\phi$?> and (ii) the number of inter-cluster edges is at most <?TeX $\epsilon |E|$?>. We show that an <?TeX $(\epsilon ,\phi)$?>-expander decomposition with <?TeX $\phi =(\epsilon /\log n)^{2^{O(k)}}$?> can be constructed in <?TeX $O(n^{2/k}\cdot {\operatorname{poly}}(1/\phi ,\log n))$?> rounds for any <?TeX $\epsilon \in (0,1)$?> and positive integer <?TeX $k$?>. For example, a <?TeX $(1/n^{o(1)},1/n^{o(1)})$?>-expander decomposition only requires <?TeX $n^{o(1)}$?> rounds to compute, which is optimal up to subpolynomial factors, and a <?TeX $\left(0.1, 1/{\operatorname{poly}}\log n\right)$?>-expander decomposition can be computed in <?TeX $O\left(n^{\gamma }\right)$?> rounds, for any arbitrarily small constant <?TeX $\gamma \gt 0$?>.Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate <?TeX $\mathsf {CONGESTED}\text{-}\mathsf {CLIQUE}$?> algorithms with small overhead by applying theexpander routingalgorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.
We present improved distributed algorithms for variants of the triangle finding problem in the <?TeX $\mathsf {CONGEST}$?> model. We show that triangle detection, counting, and enumeration can be solved in <?TeX $\tilde{O}(n^{1/3})$?> rounds usingexpander decompositions. This matches the triangle enumeration lower bound of <?TeX $\tilde{\Omega }(n^{1/3})$?> by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the <?TeX $\mathsf {CONGESTED}\text{-}\mathsf {CLIQUE}$?> model. The previous upper bounds for triangle detection and enumeration in <?TeX $\mathsf {CONGEST}$?> were <?TeX $\tilde{O}(n^{2/3})$?> and <?TeX $\tilde{O}(n^{3/4})$?>, respectively, due to Izumi and Le Gall [PODC’17].An <?TeX $(\epsilon ,\phi)$?>-expander decomposition of a graph <?TeX $G=(V,E)$?> is a clustering of the vertices <?TeX $V=V_{1}\cup \cdots \cup V_{x}$?> such that (i) each cluster <?TeX $V_{i}$?> induces a subgraph with conductance at least <?TeX $\phi$?> and (ii) the number of inter-cluster edges is at most <?TeX $\epsilon |E|$?>. We show that an <?TeX $(\epsilon ,\phi)$?>-expander decomposition with <?TeX $\phi =(\epsilon /\log n)^{2^{O(k)}}$?> can be constructed in <?TeX $O(n^{2/k}\cdot {\operatorname{poly}}(1/\phi ,\log n))$?> rounds for any <?TeX $\epsilon \in (0,1)$?> and positive integer <?TeX $k$?>. For example, a <?TeX $(1/n^{o(1)},1/n^{o(1)})$?>-expander decomposition only requires <?TeX $n^{o(1)}$?> rounds to compute, which is optimal up to subpolynomial factors, and a <?TeX $\left(0.1, 1/{\operatorname{poly}}\log n\right)$?>-expander decomposition can be computed in <?TeX $O\left(n^{\gamma }\right)$?> rounds, for any arbitrarily small constant <?TeX $\gamma \gt 0$?>.Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate <?TeX $\mathsf {CONGESTED}\text{-}\mathsf {CLIQUE}$?> algorithms with small overhead by applying theexpander routingalgorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.
登录
查看更多内容
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：
--
发表时间：
2016
期刊：
ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing
影响因子：
--
作者：
Michael Elkin;Ofer Neiman
通讯作者：
Ofer Neiman
分布式子图检测的可能性和不可能性
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
平面网络的分布式算法 I：平面嵌入
DOI：
10.1145/2933057.2933109
发表时间：
2016
期刊：
Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing
影响因子：
--
作者：
M. Ghaffari;Bernhard Haeupler
通讯作者：
Bernhard Haeupler