---
_id: '11865'
abstract:
- lang: eng
  text: We present the first sublinear-time algorithm that can compute the edge connectivity
    λ of a network exactly on distributed message-passing networks (the CONGEST model),
    as long as the network contains no multi-edge. We present the first sublinear-time
    algorithm for a distributed message-passing network sto 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: Mohit
  full_name: Daga, Mohit
  last_name: Daga
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Danupon
  full_name: Nanongkai, Danupon
  last_name: Nanongkai
- first_name: Thatchaphol
  full_name: Saranurak, Thatchaphol
  last_name: Saranurak
citation:
  ama: 'Daga M, Henzinger MH, Nanongkai D, Saranurak T. Distributed edge connectivity
    in sublinear time. In: <i>Proceedings of the 51st Annual ACM SIGACT Symposium
    on Theory of Computing</i>. Association for Computing Machinery; 2019:343–354.
    doi:<a href="https://doi.org/10.1145/3313276.3316346">10.1145/3313276.3316346</a>'
  apa: 'Daga, M., Henzinger, M. H., Nanongkai, D., &#38; Saranurak, T. (2019). Distributed
    edge connectivity in sublinear time. In <i>Proceedings of the 51st Annual ACM
    SIGACT Symposium on Theory of Computing</i> (pp. 343–354). Phoenix, AZ, United
    States: Association for Computing Machinery. <a href="https://doi.org/10.1145/3313276.3316346">https://doi.org/10.1145/3313276.3316346</a>'
  chicago: Daga, Mohit, Monika H Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak.
    “Distributed Edge Connectivity in Sublinear Time.” In <i>Proceedings of the 51st
    Annual ACM SIGACT Symposium on Theory of Computing</i>, 343–354. Association for
    Computing Machinery, 2019. <a href="https://doi.org/10.1145/3313276.3316346">https://doi.org/10.1145/3313276.3316346</a>.
  ieee: M. Daga, M. H. Henzinger, D. Nanongkai, and T. Saranurak, “Distributed edge
    connectivity in sublinear time,” in <i>Proceedings of the 51st Annual ACM SIGACT
    Symposium on Theory of Computing</i>, Phoenix, AZ, United States, 2019, pp. 343–354.
  ista: 'Daga M, Henzinger MH, Nanongkai D, Saranurak T. 2019. Distributed edge connectivity
    in sublinear time. Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
    of Computing. STOC: Symposium on Theory of Computing, 343–354.'
  mla: Daga, Mohit, et al. “Distributed Edge Connectivity in Sublinear Time.” <i>Proceedings
    of the 51st Annual ACM SIGACT Symposium on Theory of Computing</i>, Association
    for Computing Machinery, 2019, pp. 343–354, doi:<a href="https://doi.org/10.1145/3313276.3316346">10.1145/3313276.3316346</a>.
  short: M. Daga, M.H. Henzinger, D. Nanongkai, T. Saranurak, in:, Proceedings of
    the 51st Annual ACM SIGACT Symposium on Theory of Computing, Association for Computing
    Machinery, 2019, pp. 343–354.
conference:
  end_date: 2019-06-26
  location: Phoenix, AZ, United States
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 2019-06-23
date_created: 2022-08-16T09:11:17Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-02-17T10:26:25Z
day: '01'
doi: 10.1145/3313276.3316346
extern: '1'
external_id:
  arxiv:
  - '1904.04341'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1904.04341
month: '06'
oa: 1
oa_version: Preprint
page: 343–354
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
publication_identifier:
  isbn:
  - 978-1-4503-6705-9
  issn:
  - 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Distributed edge connectivity in sublinear time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2019'
...