Unbalanced graph cuts with minimum capacity

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

References

[1] Armon A, Zwick U. Multicriteria global <?Pub Caret?>minimum cuts. Algorithmica, 2006, 46(1): 15-26

[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

[6] Karger D, Stein C. A new approach to the minimum cut problem. Journal of the ACM, 1996, 43(4): 601-640

[7] Feige U, Krauthgamer R, Nissim K. On cutting a few vertices from a graph. Discrete Applied Mathematics, 2003, 127: 643-49

[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

[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

[14] Krauthgamer R. Minimum bisection. In: Kao M Y, ed. Encyclopedia of Algorithms. Springer, 2008, 519-522

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg