Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Distributed edge connectivity in sublinear time
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
2019 (English)In: Proceeding STOC 2019 Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing Machinery (ACM), 2019, p. 343-354Conference paper, Published paper (Refereed)
Abstract [en]

We present the first sublinear-time algorithm for a distributed message-passing networks to compute its edge connectivity λ exactly in the CONGEST model, as long as there are no parallel edges. Our algorithm takes Õ(n1−1/353D1/353 + n1−1/706) time to compute λ and a cut of cardinality λ with high probability, where n and D are the number of nodes and the diameter of the network, respectively, and Õ hides polylogarithmic factors. This running time is sublinear in n (i.e. Õ(n1−ϵ)) whenever D is. Previous sublinear-time distributed algorithms can solve this problem either (i) exactly only when λ = O(n1/8−ϵ) [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(n1−ϵ) in time Õ(nk + D). The previous sublinear-time algorithm can do so only when k = o(n) [Thurimella PODC’95]. In fact, our algorithm can be turned into the first parallel algorithm with polylogarithmic depth and near-linear work. Previous near-linear work algorithms are essentially sequential and previous polylogarithmic-depth algorithms require Ω(mk) work in the worst case (e.g. [Karger, Motwani, STOC’93]). 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). This leads to a simplification of the Kawarabayashi-Thorup framework (except that we are randomized while they are deterministic). This might make this framework more useful in other models of computation. 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 Õ(n)-time algorithm for computing exact minimum cut for weighted graphs.

Place, publisher, year, edition, pages
Association for Computing Machinery (ACM), 2019. p. 343-354
Series
Proceedings of the Annual ACM Symposium on Theory of Computing, ISSN 0737-8017
Keywords [en]
Distributed computing, Edge connectivity, Graph algorithms
National Category
Computer and Information Sciences
Identifiers
URN: urn:nbn:se:kth:diva-262619DOI: 10.1145/3313276.3316346Scopus ID: 2-s2.0-85068761218ISBN: 9781450367059 (print)OAI: oai:DiVA.org:kth-262619DiVA, id: diva2:1365385
Conference
51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019; Phoenix; United States; 23 June 2019 through 26 June 2019
Note

QC 20191024

Available from: 2019-10-24 Created: 2019-10-24 Last updated: 2019-10-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Daga, MohitNanongkai, Danupon
By organisation
Theoretical Computer Science, TCS
Computer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 37 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf