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...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 re- cently 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.展开更多
基金We thank the anonymous reviewers for their sugges- tions which help to improve the presentation of the paper. Part of this work was completed while visiting Microsoft Research Asia. We are grateful for the helpful discussions with Wei Chen, Pinyan Lu, and Yajun Wang （Theory Group, Microsoft Research Asia） on this topic. This work was supported by the National Natural Science Foundation of China （Grant No. 60970003）, the StarTrack Program of Microsoft Research Asia, the State Scholarship Fund of China, and the Independent Innovation Foundation of Shandong University （2012TS072）.
文摘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 re- cently 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.
基金Acknowledgments： The authors thank for Prof. ZHANG Rong＇s valuable comments that improve the readability of this paper. This work was supported by the National Natural Science Foundation of China （No. 60672071）, the Ministry of Education （No. NCET-05-0534）, the Natural Science Foundation of Zhejiang （No. D 1080807）.
