Distributed weighted min-cut in nearly-optimal time

DOI10.1145/3406325.3451020arXiv2004.09129OpenAlexW3168134475WikidataQ130868617 ScholiaQ130868617MaRDI QIDQ6065239FDOQ6065239

Authors: Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, Danupon Nanongkai 

Publication date: 14 November 2023

Published in: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Abstract: Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]) can guarantee a solution that is $(1+epsilon)$-approximation at best while the exact $ildeO(n^{0.8}{D}^{0.2}+n^{0.9})$-time algorithm [Ghaffari, Nowicki, Thorup, SODA'20] works only on *simple* networks (no weights and no parallel edges). Here $n$ and $D$ denote the network's number of vertices and hop-diameter, respectively. For the weighted case, the best bound was $ildeO(n)$ [Daga, Henzinger, Nanongkai, Saranurak, STOC'19]. In this paper, we provide an *exact* $ildeO(sqrtn+D)$-time algorithm for computing min-cut on *weighted* networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a clever routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC'20] and can be of independent interest.

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

zbMATH Keywords

CONGEST modelminimun-cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cited In (4)

• Near-optimal distributed computation of small vertex cuts
• An optimal pruned traversal tree-based fast minimum cut solver in dense graph
• Almost-Tight Distributed Minimum Cut Algorithms
• Finding a small vertex cut on distributed networks

This page was built for publication: Distributed weighted min-cut in nearly-optimal time

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