Improved distributed expander decomposition and nearly optimal triangle enumeration

DOI10.1145/3293611.3331618MaRDI QIDQ5145182zbMATH OpenOpenAlexWikidataFDO

Authors Yi-Jun Chang, Thatchaphol Saranurak

Publication date 20 January 2021

Published in Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1904.08037

zbMATH Keywords

expander decompositionlow-diameter decompositiontriangle enumeration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15) Approximation algorithms (68W25)

Abstract: An $(epsilon,phi)$-expander decomposition of a graph $G=(V,E)$ is a clustering of the vertices $V=V_{1}cupcdotscup{V}_x$ such that (1) each cluster $V_i$ induces subgraph with conductance at least $phi$, and (2) the number of inter-cluster edges is at most $epsilon|E|$. In this paper, we give an improved distributed expander decomposition. Specifically, we construct an $(epsilon,phi)$-expander decomposition with $phi=(epsilon/logn{)}^{2^{O(k)}}$ in $O(n^{2/k}cdotextpoly(1/phi,logn))$ rounds for any $epsilonin(0,1)$ and positive integer $k$. For example, a $(0.01,1/extpolylogn)$-expander decomposition can be computed in $O(n^{gamma})$ rounds, for any arbitrarily small constant $gamma>0$. Previously, the algorithm by Chang, Pettie, and Zhang can construct a $(1/6,1/extpolylogn)$-expander decomposition using $ildeO(n^{1-delta})$ rounds for any $delta>0$, with a caveat that the algorithm is allowed to throw away a set of edges into an extra part which forms a subgraph with arboricity at most $n^{delta}$. 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 $ildeO(n^{1/3})$ rounds. This matches the lower bound by Izumi and Le Gall [PODC'17] and Pandurangan, Robinson and Scquizzato [SPAA'18] of $ildeOmega(n^{1/3})$ which holds even in the CONGESTED CLIQUE model. 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.

Recommendations

• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Distributed triangle detection via expander decomposition
• Expander decomposition and pruning: faster, stronger, and simpler
• Triangle Finding and Listing in CONGEST Networks
• Distributed sparse cut approximation

Cited in

(23)

• Distributed detection of clusters of arbitrary size
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• Detecting cliques in CONGEST networks
• Fooling views: a new lower bound technique for distributed computations under congestion
• A note on improved results for one round distributed clique listing
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• Optimal short cycle decomposition in almost linear time
• Finding a bounded-degree expander inside a dense one
• Distributed triangle detection via expander decomposition
• Expander decomposition and pruning: faster, stronger, and simpler
• The communication complexity of set intersection and multiple equality testing
• Expanders via local edge flips in quasilinear time
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Towards the Erdős-Gallai cycle decomposition conjecture
• Finding a small vertex cut on distributed networks
• Fast distributed algorithms for girth, cycles and small subgraphs
• Deterministic near-optimal distributed listing of cliques
• On the streaming complexity of expander decomposition
• A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}
• Even-cycle detection in the randomized and quantum CONGEST model
• Distributed subgraph finding: progress and challenges (invited talk)
• Worst-case to expander-case reductions: derandomized and generalized
• Length-constrained directed expander decomposition and length-constrained vertex-capacitated flow shortcuts

This page was built for publication: Improved distributed expander decomposition and nearly optimal triangle enumeration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5145182)