Best Paper Award

Mohsen Ghaffari and Fabian Kuhn received the best paper award of DISC 2013 for their paper Distributed Minimum Cut Approximation.

Mohsen Ghaffari and Fabian Kuhn received the best paper award of DISC 2013 for their paper Distributed Minimum Cut Approximation.

We study the problem of computing approximate minimum edge cutsby distributed algorithms. We use a standard synchronous message passing modelwhere in each round,O(logn)bits can be transmitted over each edge (a.k.a. theCONGESTmodel). The first algorithm is based on a simple and new approach foranalyzing random edge sampling, which we call therandom layering technique.For any weighted graph and anyǫ(0,1), the algorithm with high probabilityfinds a cut of size at mostO(ǫ1λ)inO(D) + ̃O(n1/2+ǫ)rounds, whereλisthe size of the minimum cut and the ̃O-notation hides poly-logarithmic factors inn. In addition, based on a centralized algorithm due to Matula [SODA ’93], wepresent a randomized distributed algorithm that with high probability computes acut of size at most(2 +ǫ)λin ̃O((D+n)5)rounds for anyǫ >0.The time complexities of our algorithms almost match the ̃(D+n)lowerbound of Das Sarma et al. [STOC ’11], thus leading to an answer to an openquestion raised by Elkin [SIGACT-News ’04] and Das Sarma et al. [STOC ’11].To complement our upper bound results, we also strengthen the ̃(D+n)lowerbound of Das Sarma et al. by extending it to unweighted graphs. We showthatthe same lower bound also holds for unweighted multigraphs (or equivalently forweighted graphs in whichO(wlogn)bits can be transmitted in each round overan edge of weightw). For unweighted simple graphs, we show that computing anα-approximate minimum cut requires time at least ̃(D+n/α1/4).