Improved distributed expander decomposition and nearly optimal triangle enumeration

DOI10.1145/3293611.3331618MaRDI QIDQ5145182zbMATHOpenAlexWikidataFDO

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

low-diameter decompositiontriangle enumerationexpander decomposition

Mathematics Subject Classification ID

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

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

(16)

• Detecting cliques in CONGEST networks
• Towards the Erdős-Gallai cycle decomposition conjecture
• The communication complexity of set intersection and multiple equality testing
• Deterministic near-optimal distributed listing of cliques
• Distributed detection of clusters of arbitrary size
• Finding a small vertex cut on distributed networks
• Near-optimal Distributed Triangle Enumeration via Expander Decompositions
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Expander decomposition and pruning: faster, stronger, and simpler
• Expanders via local edge flips in quasilinear time
• Finding a bounded-degree expander inside a dense one
• Fooling views: a new lower bound technique for distributed computations under congestion
• A note on improved results for one round distributed clique listing
• Distributed triangle detection via expander decomposition
• Fast distributed algorithms for girth, cycles and small subgraphs
• Sublinear-time distributed algorithms for detecting small cliques and even cycles

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)