Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Unbalanced graph cuts with minimum capacity

  • Research Article
  • Published:
Frontiers of Computer Science Aims and scope Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Armon A, Zwick U. Multicriteria global minimum cuts. Algorithmica, 2006, 46(1): 15–26

    Article  MATH  MathSciNet  Google Scholar 

  2. Feige U, Krauthgamer R. A polylogarithmic approximation of the minimum bisection. Society for Industrial and Applied Mathematics Review, 2006, 48(1): 99–130

    MATH  MathSciNet  Google Scholar 

  3. Räcke H. Optimal hierarchical decompositions for congestionminimization in networks. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing. 2008, 255–264

    Google Scholar 

  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

    Google Scholar 

  5. Garey M, Johnson D, Stockmeyer L. Some simplified NP-complete graph problems. Theoretical Computer Science, 1976, 1: 237–267

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  7. Feige U, Krauthgamer R, Nissim K. On cutting a few vertices from a graph. Discrete Applied Mathematics, 2003, 127: 643–649

    Article  MATH  MathSciNet  Google Scholar 

  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

    MATH  MathSciNet  Google Scholar 

  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

    Google Scholar 

  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

    Chapter  Google Scholar 

  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

    Google Scholar 

  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

    Google Scholar 

  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

    Article  MATH  MathSciNet  Google Scholar 

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

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Technology, Shandong University, Jinan, 250101, China

    Peng Zhang

Authors
  1. Peng Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Peng Zhang.

Additional information

Peng Zhang is an associate professor of computer science at the School of Computer Science and Technology, Shandong University, China. He received his PhD in computer science from the Institute of Software, Chinese Academy of Sciences in 2007. His research interests include approximation algorithms, combinatorial optimization, and computational complexity. He has published more than twenty papers, mainly in approximation algorithms, in journals such as Theory of Computing Systems, Discrete Applied Mathematics, Theoretical Computer Science, and in conferences such as ISAAC, LATIN, COCOA, and TAMC.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Zhang, P. Unbalanced graph cuts with minimum capacity. Front. Comput. Sci. 8, 676–683 (2014). https://doi.org/10.1007/s11704-014-3289-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11704-014-3289-1

Keywords

Search

Navigation