Universally-Optimal Distributed Exact Min-Cut

DOI10.1145/3519270.3538429MaRDI QIDQ6202172zbMATH OpenOpenAlexWikidataFDO

Authors Mohsen Ghaffari, Goran Zuzic

Publication date 26 March 2024

Published in Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

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

zbMATH Keywords

congest modeldistributed algorithmsexact minimum cutlow-congestion shortcutsmessage-passing algorithmsminor-aggregation modeluniversal optimality

Mathematics Subject Classification ID

Distributed systems (68M14) Distributed algorithms (68W15)

Abstract: We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in $widetildeO(D+sqrtn)$ rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai~[STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in $widetildeO(D)$ rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family. We obtain this result by designing an aggregation-based algorithm: each node receives only an aggregate of the messages sent to it. While somewhat restrictive, recent work shows any such black-box algorithm can be simulated on any minor of the communication network. Furthermore, we observe this also allows for the addition of (a small number of) arbitrarily-connected virtual nodes to the network. We leverage these capabilities to design a min-cut algorithm that is significantly simpler compared to prior distributed work. We hope this paper showcases how working within this paradigm yields simple-to-design and ultra-efficient distributed algorithms for global problems. Our main technical contribution is a distributed algorithm that, given any tree $T$, computes the minimum cut that $2$-respects $T$ (i.e., cuts at most $2$ edges of $T$) in universally near-optimal time. Moreover, our algorithm gives a emph{deterministic} $widetildeO(D)$-round 2-respecting cut solution for excluded-minor families and a emph{deterministic} $widetildeO(D+sqrtn)$-round solution for general graphs, the latter resolving a question of Dory, et al.~[STOC'21]

Cited in

(1)

• High-speed minimum cut approximation in dense graph using compacted pruned tree

This page was built for publication: Universally-Optimal Distributed Exact Min-Cut

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