Distributed Minimum Cut Approximation


We study the problem of computing approximate minimum edge cuts by distributed algorithms. We present two randomized approximation algorithms that both run in a standard synchronous message passing model where in each round, $O(log n)$ bits can be transmitted over every 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 random layering technique. For any any weighted graph and any $\epsilon \in (0, 1)$, the algorithm finds a cut of size at most $O(\epsilon^{-1}\lambda)$ in $O(D) + \tilde{O}(n^{1/2 + \epsilon})$ rounds, where $\lambda$ is the minimum-cut size and the $\tilde{O}$-notation hides poly-logarithmic factors in $n$. In addition, using the outline of a centralized algorithm due to Matula [SODA '93], we present a randomized algorithm to compute a cut of size at most $(2+\epsilon)\lambda$ in $\tilde{O}((D+\sqrt{n})/\epsilon^5)$ rounds for any $\epsilon>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 $\alpha$-approximate minimum cut requires time at least $\tilde{\Omega}(D + \sqrt{n}/\alpha^{1/4})$.

Guest: Mohsen Ghaffari (Electrical Engineering and Computer Science Department, Massachusetts Institute of Technology)

Host: Merav Parter

Approximate Duality of Multicommodity Multiroute Flows and Cuts: Single Source Case

Petr Kolman and Christian Scheideler


Given an integer h, a graph with arbitrary positive edge capacities and k pairs of vertices , called terminals, an h-route cut is a set of edges such that after the removal of the edges in F no pair is connected by h edge-disjoint paths (i.e., the connectivity of every pair is at most in . The h-route cut is a natural generalization of the classical cut problem for multicommodity flows (take h = 1). The main result of this paper is an -approximation algorithm for the minimum h-route cut problem in the case that , called the single source case. As a corollary of it we obtain an approximate duality theorem for multiroute multicommodity flows and cuts with a single source. This partially answers an open question posted in several previous papers dealing with cuts for multicommodity multiroute problems.

Guest: Christian Scheideler
Host: Shantanu Das