Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

Postal Subscription Code 80-970

2018 Impact Factor: 1.129

Front. Comput. Sci.    2014, Vol. 8 Issue (4) : 676-683    https://doi.org/10.1007/s11704-014-3289-1
RESEARCH ARTICLE
Unbalanced graph cuts with minimum capacity
Peng ZHANG()
School of Computer Science and Technology, Shandong University, Jinan 250101, China
 Download: PDF(256 KB)  
 Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks
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
 Cite this article:   
Peng ZHANG. Unbalanced graph cuts with minimum capacity[J]. Front. Comput. Sci., 2014, 8(4): 676-683.
 URL:  
https://academic.hep.com.cn/fcs/EN/10.1007/s11704-014-3289-1
https://academic.hep.com.cn/fcs/EN/Y2014/V8/I4/676
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
[1] Gang WU, Zhiyong CHEN, Jia LIU, Donghong HAN, Baiyou QIAO. Task assignment for social-oriented crowdsourcing[J]. Front. Comput. Sci., 2021, 15(2): 152316-.
[2] Ruidong YAN, Yi LI, Deying LI, Weili WU, Yongcai WANG. SSDBA: the stretch shrink distance based algorithm for link prediction in social networks[J]. Front. Comput. Sci., 2021, 15(1): 151301-.
[3] Ildar NURGALIEV, Qiang QU, Seyed Mojtaba Hosseini BAMAKAN, Muhammad MUZAMMAL. Matching user identities across social networks with limited profile data[J]. Front. Comput. Sci., 2020, 14(6): 146809-.
[4] Yiteng PAN, Fazhi HE, Haiping YU. A correlative denoising autoencoder to model social influence for top-N recommender system[J]. Front. Comput. Sci., 2020, 14(3): 143301-.
[5] Yudong QIN, Deke GUO, Zhiyao HU, Bangbang REN. Uncertain multicast under dynamic behaviors[J]. Front. Comput. Sci., 2020, 14(1): 130-145.
[6] Kai LI, Guangyi LV, Zhefeng WANG, Qi LIU, Enhong CHEN, Lisheng QIAO. Understanding the mechanism of social tie in the propagation process of social network with communication channel[J]. Front. Comput. Sci., 2019, 13(6): 1296-1308.
[7] Satoshi MIYAZAWA, Xuan SONG, Tianqi XIA, Ryosuke SHIBASAKI, Hodaka KANEDA. Integrating GPS trajectory and topics from Twitter stream for human mobility estimation[J]. Front. Comput. Sci., 2019, 13(3): 460-470.
[8] Xingshen SONG, Yuexiang YANG, Yu JIANG, Kun JIANG. Optimizing partitioning strategies for faster inverted index compression[J]. Front. Comput. Sci., 2019, 13(2): 343-356.
[9] Wei-Neng CHEN, Da-Zhao TAN. Set-based discrete particle swarm optimization and its applications: a survey[J]. Front. Comput. Sci., 2018, 12(2): 203-216.
[10] Zhongqing WANG, Shoushan LI, Guodong ZHOU. Personal summarization from profile networks[J]. Front. Comput. Sci., 2017, 11(6): 1085-1097.
[11] Yuan SU,Xi ZHANG,Lixin LIU,Shouyou SONG,Binxing FANG. Understanding information interactions in diffusion: an evolutionary game-theoretic perspective[J]. Front. Comput. Sci., 2016, 10(3): 518-531.
[12] Siyuan LIU,Shuhui WANG,Ce LIU,Ramayya KRISHNAN. Understanding taxi drivers’ routing choices from spatial and social traces[J]. Front. Comput. Sci., 2015, 9(2): 200-209.
[13] Rong-Hua LI, Jianquan LIU, Jeffrey Xu YU, Hanxiong CHEN, Hiroyuki KITAGAWA. Co-occurrence prediction in a large location-based social network[J]. Front Comput Sci, 2013, 7(2): 185-194.
[14] Xiaolong ZHENG, Yongguang ZHONG, Daniel ZENG, Fei-Yue WANG. Social influence and spread dynamics in social networks[J]. Front Comput Sci, 2012, 6(5): 611-620.
[15] Tao WANG, Qingpeng ZHANG, Zhong LIU, Wenli LIU, Ding WEN. On social computing research collaboration patterns: a social network perspective[J]. Front Comput Sci, 2012, 6(1): 122-130.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed