A distributed minimum cut approximation scheme
Hsin-Hao Su · 2014
In this paper, we study the problem of approximating the minimum cut in a distributed message-passing model, the CONGEST model. The minimum cut problem has been well-studied in the context of centralized algorithms. However, there were no known non-trivial algorithms in the distributed model until the recent work of Ghaffari and Kuhn. They gave randomized algorithms for finding cuts of size O(ε-1λ) and (2 + ε)λ in O(D) + Õ(n1/2+ε) rounds and Õ(D + √n) rounds respectively, where λ is the size of the minimum cut. This matches the lower bound they provided up to a polylogarithmic factor. Yet, no scheme that achieves (1 + ε)-approximation ratio is known. We give a distributed randomized algorithm that finds a cut of size (1 + ε)λ in Õ(D + √n) time, which is optimal up to polylogarithmic factors.