|
|
Unbalanced graph cuts with minimum capacity |
Peng ZHANG( ) |
School of Computer Science and Technology, Shandong University, Jinan 250101, China |
|
|
Abstract We systematically investigate minimum capacity unbalanced cut problems arising in social networks. Let k be an input parameter. A cut (A, B) is unbalanced if the size of its smaller side is at most k (called k-size) or exactly k (called Ek-size). An s-t cut (A, B) is unbalanced if its s-side is either k-size or Ek-size. In the min k-size cut (s-t cut, resp.) problem, we want to find a k-size cut (s-t cut, resp.) with the minimum capacity. The corresponding min Ek-size cut (and s-t cut) problem is defined in a similar way. While the classical min s-t cut problem has been studied extensively, the minimum capacity unbalanced cut problem has only recently attracted the attention of researchers. In this paper, we prove that the min k-size s-t cut problem is NP-hard, and give O(log n)-approximation algorithms for the min k-size s-t cut problem, the min Ek-size s-t cut problem, and the min Eksize cut problem. These results, together with previous results, complete our research into minimum capacity unbalanced cut problems.
|
Keywords
unbalanced cut
min cut
approximation algorithm
social network
combinatorial optimization
|
Corresponding Author(s):
Peng ZHANG
|
Issue Date: 11 August 2014
|
|
1 |
Armon A, Zwick U. Multicriteria global <?Pub Caret?>minimum cuts. Algorithmica, 2006, 46(1): 15-26 doi: 10.1007/s00453-006-0068-x
|
2 |
Feige U, Krauthgamer R. A polylogarithmic approximation of the minimum bisection. Society for Industrial and Applied Mathematics Review, 2006, 48(1): 99-130
|
3 |
R?cke H. Optimal hierarchical decompositions for congestionmini-mization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 255-264
|
4 |
Li A, Zhang P. Unbalanced graph partitioning. In: Cheong O, Chwa K Y, Park K, eds. Proceedings of the 21st International Symposium on Algorithms and Computation, Part I. 2010, 218-229
|
5 |
Garey M, Johnson D, Stockmeyer L. Some simplified NP-complete graph problems. Theoretical Computer Science, 1976, 1: 237-267 doi: 10.1016/0304-3975(76)90059-1
|
6 |
Karger D, Stein C. A new approach to the minimum cut problem. Journal of the ACM, 1996, 43(4): 601-640 doi: 10.1145/234533.234534
|
7 |
Feige U, Krauthgamer R, Nissim K. On cutting a few vertices from a graph. Discrete Applied Mathematics, 2003, 127: 643-49 doi: 10.1016/S0166-218X(02)00394-3
|
8 |
Nagamochi H, Nishimura K, Ibaraki T. Computing all small cuts in an undirected network. Society for Industrial and Applied Mathematics Journal on Discrete Mathematics, 1997, 10(3): 469-481
|
9 |
Hayrapetyan A, Kempe D, Pál M, Svitkina Z. Unbalanced graph cuts. In: Brodal G, Leonardi S, eds. Proceedings of the 13th Annual European Symposium on Algorithms. 2005, 191-202
|
10 |
Svitkina Z, Tardos E. Min-max multiway cut. In: Jansen K, Khanna S, Rolim J, Ron D, eds. Proceedings of the 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems. 2004, 207-218 doi: 10.1007/978-3-540-27821-4_19
|
11 |
Fomin F, Golovach P, Korhonen J. On the parameterized complexity of cutting a few vertices from a graph. arXiv:1304.6189, 2013, 1-12
|
12 |
Chuzhoy J, Makarychev Y, Vijayaraghavan A, Zhou Y. Approximation algorithms and hardness of the k-route cut problem. In: Proceedings of the 23rd Annual ACM-Society for Industrial and Applied Mathematics Symposium on Discrete Algorithms. 2012, 780-799
|
13 |
Fakcharoenphol J, Rao S, Talwar K. A tight bound on approximating arbitrary metrics by tree metrics. Journal of Computer and System Sciences, 2004, 69(3): 485-497 doi: 10.1016/j.jcss.2004.04.011
|
14 |
Krauthgamer R. Minimum bisection. In: Kao M Y, ed. Encyclopedia of Algorithms. Springer, 2008, 519-522 doi: 10.1007/978-0-387-30162-4_231
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
|
Shared |
|
|
|
|
|
Discussed |
|
|
|
|