Universally-Optimal Distributed Exact Min-Cut
Mohsen Ghaffari, Goran Žužić · 2022
We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in Õ(D + √n ) 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 Õ(D) rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family.