Distributed edge connectivity in sublinear time

DOI10.1145/3313276.3316346MaRDI QIDQ5212776zbMATH OpenOpenAlexWikidataFDO

Authors Mohit Daga, Danupon Nanongkai, Thatchaphol Saranurak, Monika R. Henzinger

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

distributed computinggraph algorithmsedge connectivityCONGEST

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Connectivity (05C40) Distributed algorithms (68W15)

Abstract: We present the first sublinear-time algorithm for a distributed message-passing network sto compute its edge connectivity $lambda$ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes $ildeO(n^{1-1/353}{D}^{1/353}+n^{1-1/706})$ time to compute $lambda$ and a cut of cardinality $lambda$ with high probability, where $n$ and $D$ are the number of nodes and the diameter of the network, respectively, and $ildeO$ hides polylogarithmic factors. This running time is sublinear in $n$ (i.e. $ildeO(n^{1-epsilon})$) whenever $D$ is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when $lambda=O(n^{1/8-epsilon})$ [Thurimella PODC'95; Pritchard, Thurimella, ACM Trans. Algorithms'11; Nanongkai, Su, DISC'14] or (ii) approximately [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]. To achieve this we develop and combine several new techniques. First, we design the first distributed algorithm that can compute a $k$-edge connectivity certificate for any $k=O(n^{1-epsilon})$ in time $ildeO(sqrtnk+D)$. Second, we show that by combining the recent distributed expander decomposition technique of [Chang, Pettie, Zhang, SODA'19] with techniques from the sequential deterministic edge connectivity algorithm of [Kawarabayashi, Thorup, STOC'15], we can decompose the network into a sublinear number of clusters with small average diameter and without any mincut separating a cluster (except the `trivial' ones). Finally, by extending the tree packing technique from [Karger STOC'96], we can find the minimum cut in time proportional to the number of components. As a byproduct of this technique, we obtain an $ildeO(n)$-time algorithm for computing exact minimum cut for weighted graphs.

Recommendations

• Almost-Tight Distributed Minimum Cut Algorithms
• scientific article; zbMATH DE number 437577
• Fast Distributed Computation of Cuts Via Random Circulations
• Deterministic Edge Connectivity in Near-Linear Time
• Small cuts and connectivity certificates: a fault tolerant approach

Cited in

(14)

• Small cuts and connectivity certificates: a fault tolerant approach
• Sublinear-time distributed algorithms for detecting small cliques and even cycles
• AN EFFICIENT DISTRIBUTED ALGORITHM FOR 3-EDGE-CONNECTIVITY
• scientific article; zbMATH DE number 437577 (Why is no real title available?)
• Testing connectivity of faulty networks in sublinear time
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• On packing low-diameter spanning trees
• Distributed Computing - IWDC 2004
• Sub-linear Distributed Algorithms for Sparse Certificates and Biconnected Components
• Linear time distributed swap edge algorithms
• Finding a small vertex cut on distributed networks
• Tree-packing revisited: faster fully dynamic min-cut and arboricity
• Stochastic distance in property testing
• Deterministic Edge Connectivity in Near-Linear Time

This page was built for publication: Distributed edge connectivity in sublinear time

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