Distributed Minimum Cut Approximation

We study the problem of computing approximate minimum edge cuts by distributed algorithms. We use a standard synchronous message passing model where in each round,

O

(log

n

) bits can be transmitted over each edge (a.k.a. the

CONGEST

model). The first algorithm is based on a simple and new approach for analyzing random edge sampling, which we call the

random layering technique

. For any weighted graph and any

ε

 ∈ (0, 1), the algorithm with high probability finds a cut of size at most

O

(

ε

− 1

λ

) in

$O(D) + \tilde{O}(n^{1/2 + \epsilon})$

rounds, where

λ

is the size of the minimum cut and the

$\tilde{O}$

-notation hides poly-logarithmic factors in

n

. In addition, based on a centralized algorithm due to Matula [SODA ’93], we present a randomized distributed algorithm that with high probability computes a cut of size at most (2 + 

ε

)

λ

in

$\tilde{O}((D+\sqrt{n})/\epsilon^5)$

rounds for any

ε

 > 0.

The time complexities of our algorithms almost match the

$\tilde{\Omega}(D + \sqrt{n})$

lower bound of Das Sarma et al. [STOC ’11], thus leading to an answer to an open question raised by Elkin [SIGACT-News ’04] and Das Sarma et al. [STOC ’11].

To complement our upper bound results, we also strengthen the

$\tilde{\Omega}(D + \sqrt{n})$

lower bound of Das Sarma et al. by extending it to unweighted graphs. We show that the same lower bound also holds for unweighted multigraphs (or equivalently for weighted graphs in which

O

(

w

log

n

) bits can be transmitted in each round over an edge of weight

w

). For unweighted simple graphs, we show that computing an

α

-approximate minimum cut requires time at least

$\tilde{\Omega}(D + \sqrt{n}/\alpha^{1/4})$

.