��������

Skip to main content

Advertisement

Springer Nature Link
Log in

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

For an edge-weighted connected undirected graph, the minimum k-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into k connected components. The problem is NP-hard when k is part of the input and W[1]-hard when k is taken as a parameter.

A simple algorithm for approximating a minimum k-way cut is to iteratively increase the number of components of the graph by h�?, where 2�?i>h�?i>k, until the graph has k components. The approximation ratio of this algorithm is known for h�? but is open for h�?.

In this paper, we consider a general algorithm that successively increases the number of components of the graph by h i �?, where 2�?i>h 1�?i>h 2�?i>⋅⋅�?/i>�?i>h q and �?span class="c-stack"> qi=1 (h i �?)=k�?. We prove that the approximation ratio of this general algorithm is \(2-(\sum_{i=1}^{q}{h_{i}\choose2})/{k\choose2}\) , which is tight. Our result implies that the approximation ratio of the simple iterative algorithm is 2�?i>h/k+O(h 2/k 2) in general and 2�?i>h/k if k�? is a multiple of h�?.

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
�?2.70 /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 includes VAT (China (P.R.))

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles and news from researchers in related subjects, suggested using machine learning.

References

  1. Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24�?7 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  2. Thorup, M.: Minimum k-way cuts via deterministic greedy tree packing. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC�?8), pp. 159�?65. ACM, Victoria (2008)

    Google Scholar 

  3. Karger, D.R., Stein, C.: A new approach to the minimum cut problem. J. ACM 43(4), 601�?40 (1996)

    MATH  MathSciNet  Google Scholar 

  4. Downey, R.G., Estivill-Castro, V., Fellows, M.R., Prieto, E., Rosamond, F.A.: Cutting up is hard to do: the parameterized complexity of k-cut and related problems. Electr. Notes Theor. Comput. Sci. 78, 1�?4 (2003)

    Article  Google Scholar 

  5. Hao, J., Orlin, J.B.: A faster algorithm for finding the minimum cut in a graph. In: Proceedings of the 3rd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA�?2), pp. 165�?74. Society for Industrial and Applied Mathematics, Philadelphia (1992)

    Google Scholar 

  6. Nagamochi, H., Ibaraki, T.: Computing edge connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math. 5(1), 54�?6 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  7. Burlet, M., Goldschmidt, O.: A new and improved algorithm for the 3-cut problem. Oper. Res. Lett. 21(5), 225�?27 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  8. Nagamochi, H., Ibaraki, T.: A fast algorithm for computing minimum 3-way and 4-way cuts. Math. Program. 88(3), 507�?20 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  9. Nagamochi, H., Katayama, S., Ibaraki, T.: A faster algorithm for computing minimum 5-way and 6-way cuts in graphs. In: Computing and Combinatorics Conference (COCOON�?9). LNCS, vol. 1627, pp. 164�?73. Springer, Berlin (1999)

    Chapter  Google Scholar 

  10. Levine, M.S.: Fast randomized algorithms for computing minimum {3,4,5,6}-way cuts. In: Proceedings of the 11th Annual ACM–SIAM Symposium on Discrete Algorithms (SODA�?0), pp. 735�?42. Society for Industrial and Applied Mathematics, Philadelphia (2000)

    Google Scholar 

  11. Saran, H., Vazirani, V.V.: Finding k-cuts within twice the optimal. SIAM J. Comput. 24(1), 101�?08 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  12. Naor, J., Rabani, Y.: Tree packing and approximating k-cuts. In: Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA�?1), pp. 26�?7. Society for Industrial and Applied Mathematics, Philadelphia (2001)

    Google Scholar 

  13. Ravi, R., Sinha, A.: Approximating k-cuts via network strength. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA�?2), pp. 621�?22. Society for Industrial and Applied Mathematics, Philadelphia (2002)

    Google Scholar 

  14. Kapoor, S.: On minimum 3-cuts and approximating k-cuts using cut trees. In: Proceedings of the 5th International IPCO Conference on Integer Programming and Combinatorial Optimization, pp. 132�?46. Springer, London (1996)

    Google Scholar 

  15. Zhao, L., Nagamochi, H., Ibaraki, T.: Approximating the minimum k-way cut in a graph via minimum 3-way cuts. J. Comb. Optim. 5(4), 397�?10 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  16. Zhao, L., Nagamochi, H., Ibaraki, T.: Greedy splitting algorithms for approximating multiway partition problems. Math. Program. 102(1), 167�?83 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  17. Zhao, L., Nagamochi, H., Ibaraki, T.: On generalized greedy splitting algorithms for multiway partition problems. Discrete Appl. Math. 143(1�?), 130�?43 (2004)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Computer Science and Engineering, University of Electronic Science and Technology of China, Chengdu, 610054, China

    Mingyu Xiao

  2. Department of Computer Science and Engineering, The Chinese University of Hong Kong, Shatin, Hong Kong SAR, China

    Leizhen Cai & Andrew Chi-Chih Yao

  3. Institute for Theoretical Computer Science, Tsinghua University, Beijing, 100084, China

    Andrew Chi-Chih Yao

Authors
  1. Mingyu Xiao
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Leizhen Cai
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Andrew Chi-Chih Yao
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Leizhen Cai.

Additional information

L. Cai was partially supported by Earmarked Research Grant 410206 of the Research Grants Council of Hong Kong SAR, China.

A.C.-C. Yao was partially supported by National Basic Research Program of China Grant 2007CB807900, 2007CB807901.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Xiao, M., Cai, L. & Yao, A.CC. Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem. Algorithmica 59, 510�?20 (2011). //doi.org/10.1007/s00453-009-9316-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: //doi.org/10.1007/s00453-009-9316-1

Keywords