Abstract
Given a positive integer k and an edge-weighted undirected graph G = (V,E;w), the minimum k -way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. This problem is a natural generalization of the classical minimum cut problem and has been well-studied in the literature.
A simple and natural method to solve the minimum k-way cut problem is the divide-and-conquer method: getting a minimum k-way cut by properly separating the graph into two small graphs and then finding minimum k′-way cut and k′′-way cut respectively in the two small graphs, where k′ + k′′ = k. In this paper, we present the first algorithm for the tight case of \(k'=\lfloor k/2\rfloor\). Our algorithm runs in \(O(n^{4k-\lg k})\) time and can enumerate all minimum k-way cuts, which improves all the previously known divide-and-conquer algorithms for this problem.
The work was done when the author was a PhD student in Department of Computer Science and Engineering, the Chinese University of Hong Kong.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Burlet, M., Goldschmidt, O.: A new and improved algorithm for the 3-cut problem. Operations Research Letters 21(5), 225–227 (1997)
Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994)
Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45(5), 783–797 (1998)
Goldberg, A.V., Tarjan, R.E.: A new approach to the maximum-flow problem. J. ACM 35(4), 921–940 (1988)
Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the k-cut problem for fixed k. Mathematics of Operations Research 19(1), 24–37 (1994)
He, X.: An improved algorithm for the planar 3-cut problem. J. Algorithms 12(1), 23–37 (1991)
Ford, J.R., Fullkerson, D.R.: Flows in networks. Princeton University Press, Princeton (1962)
Kamidoi, Y., Wakabayashi, S., Yoshida, N.: A divide-and-conquer approach to the minimum k-way cut problem. Algorithmica 32(2), 262–276 (2002)
Kamidoi, Y., Yoshida, N., Nagamochi, H.: A deterministic algorithm for finding all minimum k-way cuts. SIAM Journal on Computing 36(5), 1329–1341 (2006)
Kapoor, S.: On minimum 3-cuts and approximating k-cuts using cut trees. In: Cunningham, W.H., Queyranne, M., McCormick, S.T. (eds.) IPCO 1996. LNCS, vol. 1084. Springer, Heidelberg (1996)
Karger, D.R., Stein, C.: A new approach to the minimum cut problem. Journal of the ACM 43(4), 601–640 (1996)
Nagamochi, H., Ibaraki, T.: Computing edge connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics 5(1), 54–66 (1992)
Nagamochi, H., Ibaraki, T.: A fast algorithm for computing minimum 3-way and 4-way cuts. Mathematical Programming 88(3), 507–520 (2000)
Nagamochi, H., Katayama, S., Ibaraki, T.: A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. In: Asano, T., Imai, H., Lee, D.T., Nakano, S.-i., Tokuyama, T. (eds.) COCOON 1999. LNCS, vol. 1627. Springer, Heidelberg (1999)
Nagamochi, H., Nishimura, K., Ibaraki, T.: Computing all small cuts in an undirected network. SIAM Journal on Discrete Mathematics 10(3), 469–481 (1997)
Naor, J., Rabani, Y.: Tree packing and approximating k-cuts. In: Proceedings of the twelfth annual ACM-SIAM symposium on discrete algorithms (SODA 2001). Society for Industrial and Applied Mathematics, Philadelphia (2001)
Ravi, R., Sinha, A.: Approximating k-cuts via network strength. In: Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms (SODA 2002). Society for Industrial and Applied Mathematics, Philadelphia (2002)
Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. Comput. 24(1), 101–108 (1995)
Stoer, M., Wagner, F.: A simple min-cut algorithm. J. ACM 44(4), 585–591 (1997)
Thorup, M.: Minimum k-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC 2008) (2008)
Xiao, M.: Algorithms for multiterminal cuts. In: Hirsch, E.A., Razborov, A.A., Semenov, A., Slissenko, A. (eds.) Computer Science – Theory and Applications. LNCS, vol. 5010. Springer, Heidelberg (2008)
Xiao, M.: Finding minimum 3-way cuts in hypergraphs. In: Agrawal, M., Du, D.-Z., Duan, Z., Li, A. (eds.) TAMC 2008. LNCS, vol. 4978. Springer, Heidelberg (2008)
Xiao, M., Cai, L., Yao, A.C.: Tight approximation ratio of a general greedy splitting algorithm for the minimum k-way cut problem (manuscript, 2007)
Zhao, L., Nagamochi, H., Ibaraki, T.: Approximating the minimum k-way cut in a graph via minimum 3-way cuts. J. Comb. Optim. 5(4), 397–410 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Xiao, M. (2008). An Improved Divide-and-Conquer Algorithm for Finding All Minimum k-Way Cuts. In: Hong, SH., Nagamochi, H., Fukunaga, T. (eds) Algorithms and Computation. ISAAC 2008. Lecture Notes in Computer Science, vol 5369. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-92182-0_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-92182-0_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-92181-3
Online ISBN: 978-3-540-92182-0
eBook Packages: Computer ScienceComputer Science (R0)