Paper detail

A Distributed Minimum Cut Approximation Scheme

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 algorithms for finding cuts of size $O(ε^{-1}λ)$ and $(2+ε)λ$ in $O(D)+\tilde{O}(n^{1/2+ε})$ rounds and $\tilde{O}(D+\sqrt{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 algorithm that finds a cut of size $(1+ε)λ$ in $\tilde{O}(D+\sqrt{n})$ time, which is optimal up to polylogarithmic factors.