Abstract
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(logn) 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(wlogn) 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})\).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Ahn, K.J., Guha, S., McGregor, A.: Graph sketches: sparsification, spanners, and subgraphs. In: Proc. of the 31st Symp. on Princ. of Database Sys., PODS 2012, pp. 5–14 (2012)
Censor-Hillel, K., Ghaffari, M., Kuhn, F.: A new perspective on vertex connectivity. arXiv (2013), http://arxiv.org/abs/1304.4553
Chattapodhyay, A., Pitassi, T.: The story of set disjointness. SIGACT News Complexity Theory Column 67 (2011)
Das Sarma, A., Holzer, S., Kor, L., Korman, A., Nanongkai, D., Pandurangan, G., Peleg, D., Wattenhofer, R.: Distributed verification and hardness of distributed approximation. SIAM J. on Comp. 41(5), 1235–1265 (2012)
Elias, P., Feinstein, A., Shannon, C.E.: Note on maximum flow through a network. IRE Transactions on Information Theory IT-2, 117–199 (1956)
Elkin, M.: Distributed approximation: a survey. SIGACT News 35(4), 40–57 (2004)
Ford, L.R., Fulkerson, D.R.: Flows in Networks. Princeton Univ. Press (2010)
Ford, L.R., Fulkersonn, D.R.: Maximal flow through a network. Canad. J. Math. 8, 399–404 (1956)
Gabow, H.N.: A matroid approach to finding edge connectivity and packing arborescences. In: Proc. 23rd ACM Symposium on Theory of Computing (STOC), pp. 112–122 (1991)
Ghaffari, M., Kuhn, F.: Distributed minimum cut approximation. arXiv (2013), http://arxiv.org/abs/1305.5520
Goel, A., Kapralov, M., Khanna, S.: Graph sparsification via refinement sampling. arXiv (2010), http://arxiv.org/abs/1004.4915
Kalyanasundaram, B., Schnitger, G.: The probabilistic communication complexity of set intersection. SIAM J. Discrete Math. 5(4), 545–557 (1992)
Kapralov, M.: Personal communication (August 2013)
Karger, D.R.: Global min-cuts in \(\mathcal{RNC}\), and other ramifications of a simple min-out algorithm. In: Prc. 4th ACM-SIAM Symp. on Disc. Alg. (SODA), pp. 21–30 (1993)
Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proc. 26th ACM Symposium on Theory of Computing (STOC), STOC 1994, pp. 648–657 (1994)
Karger, D.R.: Random sampling in cut, flow, and network design problems. In: Proc. 26th ACM Symposium on Theory of Computing (STOC), pp. 648–657 (1994)
Karger, D.R.: Using randomized sparsification to approximate minimum cuts. In: Proc. 5th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 424–432 (1994)
Karger, D.R.: Minimum cuts in near-linear time. In: Proc. 28th ACM Symp. on Theory of Computing (STOC), pp. 56–63 (1996)
Karger, D.R.: Minimum cuts in near-linear time. J. ACM 47(1), 46–76 (2000)
Karger, D.R., Stein, C.: An \(\tilde{O}(n^2)\) algorithm for minimum cuts. In: Proc. 25th ACM Symposium on Theory of Computing (STOC), pp. 757–765 (1993)
Knuth, D.E.: Stable Marriage and Its Relation to Other Combinatorial Problems: An Introduction to the Mathematical Analysis of Algorithms. AMS (1996)
Kutten, S., Peleg, D.: Fast distributed construction of k-dominating sets and applications. In: Proc. of the 14th Annual ACM Symp. on Principles of Dist. Comp., PODC 1995, pp. 238–251 (1995)
Lomonosov, M.V., Polesskii, V.P.: Lower bound of network reliability. Problems of Information Transmission 7, 118–123 (1971)
Matula, D.W.: A linear time 2 + ε approximation algorithm for edge connectivity. In: Proc. of the 4th Annual ACM-SIAM Symposium on Disc. Alg., SODA 1993, pp. 500–504 (1993)
Nagamochi, H., Ibaraki, T.: Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discret. Math. 5(1), 54–66 (1992)
Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. SIAM (2000)
Picard, J.C., Queyranne, M.: Selected applications of minimum cuts in networks. Infor. 20, 19–39 (1982)
Razborov, A.A.: On the distributional complexity of disjointness. Theor. Comp. Sci. 106, 385–390 (1992)
Thurimella, R.: Sub-linear distributed algorithms for sparse certificates and biconnected components. Journal of Algorithms 23(1), 160–179 (1997)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ghaffari, M., Kuhn, F. (2013). Distributed Minimum Cut Approximation. In: Afek, Y. (eds) Distributed Computing. DISC 2013. Lecture Notes in Computer Science, vol 8205. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41527-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-41527-2_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41526-5
Online ISBN: 978-3-642-41527-2
eBook Packages: Computer ScienceComputer Science (R0)