Improved Distributed Expander Decomposition and Nearly Optimal Triangle Enumeration

04/17/2019
by   Yi-Jun Chang, et al.
0

An (ϵ,ϕ)-expander decomposition of a graph G=(V,E) is a clustering of the vertices V=V_1∪...∪ V_x such that (1) each cluster V_i induces 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 in the CONGEST model. Specifically, we construct an (ϵ,ϕ)-expander decomposition with ϕ=(ϵ/ n)^2^O(k) in O(n^2/k·poly(1/ϕ, n)) rounds for any ϵ∈(0,1) and positive integer k. For example, a (0.01,1/poly n)-expander decomposition can be computed in O(n^γ) rounds, for any constant γ>0. Previously, the algorithm by Chang, Pettie, and Zhang can construct a (1/6,1/poly n)-expander decomposition using Õ(n^1-δ) rounds for any δ>0, with a caveat that the algorithm is allowed to throw away a set of edges which forms a subgraph with arboricity at most n^δ. Our algorithm does not have this caveat. By modifying the distributed algorithm for routing on expanders by Ghaffari, Kuhn and Su [PODC'17], we obtain a triangle enumeration algorithm using Õ(n^1/3) rounds. This matches the lower bound by Izumi and Le Gall [PODC'17] and Pandurangan, Robinson and Scquizzato [SPAA'18] of Ω̃(n^1/3) which holds even in the CONGESTED-CLIQUE model. To the best of our knowledge, this provides the first non-trivial example for a 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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset