Document Open Access Logo

LP Relaxation and Tree Packing for Minimum k-cuts

Authors Chandra Chekuri, Kent Quanrud, Chao Xu

PDF
Thumbnail PDF

File

OASIcs.SOSA.2019.7.pdf
  • Filesize: 484 kB
  • 18 pages

Document Identifiers

Author Details

Chandra Chekuri
Kent Quanrud
Chao Xu

Cite As Get BibTex

Chandra Chekuri, Kent Quanrud, and Chao Xu. LP Relaxation and Tree Packing for Minimum k-cuts. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SOSA.2019.7

Abstract

Karger used spanning tree packings [Karger, 2000] to derive a near linear-time randomized algorithm for the global minimum cut problem as well as a bound on the number of approximate minimum cuts. This is a different approach from his well-known random contraction algorithm [Karger, 1995; Karger and Stein, 1996]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [Thorup, 2008].
In this paper we revisit properties of an LP relaxation for k-cut proposed by Naor and Rabani [Naor and Rabani, 2001], and analyzed in [Chekuri et al., 2006]. We show that the dual of the LP yields a tree packing, that when combined with an upper bound on the integrality gap for the LP, easily and transparently extends Karger's analysis for mincut to the k-cut problem. In addition to the simplicity of the algorithm and its analysis, this allows us to improve the running time of Thorup's algorithm by a factor of n. We also improve the bound on the number of alpha-approximate k-cuts. Second, we give a simple proof that the integrality gap of the LP is 2(1-1/n). Third, we show that an optimum solution to the LP relaxation, for all values of k, is fully determined by the principal sequence of partitions of the input graph. This allows us to relate the LP relaxation to the Lagrangean relaxation approach of Barahona [Barahona, 2000] and Ravi and Sinha [Ravi and Sinha, 2008]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP. This work arose from an effort to understand and simplify the results of Thorup [Thorup, 2008].

Subject Classification

Keywords
  • k-cut
  • LP relaxation
  • tree packing

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Ajit Agrawal, Philip Klein, and R Ravi. When trees collide: An approximation algorithm for the generalized Steiner problem on networks. SIAM Journal on Computing, 24(3):440-456, 1995. Google Scholar
  2. Francisco Barahona. On the k-cut problem. Operations Research Letters, 26(3):99-105, 2000. Google Scholar
  3. Chandra Chekuri, Sudipto Guha, and Joseph Naor. The Steiner k-cut problem. SIAM Journal on Discrete Mathematics, 20(1):261-271, 2006. Google Scholar
  4. Chandra Chekuri and Kent Quanrud. Near-linear time approximation schemes for some implicit fractional packing problems. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 801-820. SIAM, 2017. Google Scholar
  5. William H Cunningham. Optimal attack and reinforcement of a network. Journal of the ACM (JACM), 32(3):549-561, 1985. Google Scholar
  6. Rodney G. Downey, Vladimir Estivill-Castro, Michael R. Fellows, Elena Prieto-Rodriguez, and Frances A. Rosamond. Cutting Up is Hard to Do: the Parameterized Complexity of k-Cut and Related Problems. Electr. Notes Theor. Comput. Sci., 78:209-222, 2003. Google Scholar
  7. Satoru Fujishige. Theory of principal partitions revisited. In Research Trends in Combinatorial Optimization, pages 127-162. Springer, 2009. Google Scholar
  8. Harold N. Gabow and K. S. Manu. Packing algorithms for arborescences (and spanning trees) in capacitated graphs. Mathematical Programming, 82(1):83-109, June 1998. Google Scholar
  9. Michel X Goemans and David P Williamson. A general approximation technique for constrained forest problems. SIAM Journal on Computing, 24(2):296-317, 1995. Google Scholar
  10. O. Goldschmidt and D.S. Hochbaum. A polynomial algorithm for the k-cut problem for fixed k. Mathematics of Operations Research, pages 24-37, 1994. Google Scholar
  11. Anupam Gupta, Euiwoong Lee, and Jason Li. Faster Exact and Approximate Algorithms for k-Cut. In Proceedings of IEEE FOCS, 2018. Google Scholar
  12. Monika Henzinger, Satish Rao, and Di Wang. Local Flow Partitioning for Faster Edge Connectivity. In Philip N. Klein, editor, Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1919-1938. SIAM, 2017. Google Scholar
  13. David R Karger. Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, February 1995. Google Scholar
  14. David R. Karger. Minimum Cuts in Near-linear Time. J. ACM, 47(1):46-76, January 2000. URL: http://dx.doi.org/10.1145/331605.331608.
  15. David R Karger and Clifford Stein. A new approach to the minimum cut problem. Journal of the ACM (JACM), 43(4):601-640, 1996. Google Scholar
  16. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic Global Minimum Cut of a Simple Graph in Near-Linear Time. In Rocco A. Servedio and Ronitt Rubinfeld, editors, Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 665-674. ACM, 2015. Google Scholar
  17. Vladimir Kolmogorov. A faster algorithm for computing the principal sequence of partitions of a graph. Algorithmica, 56(4):394-412, 2010. Google Scholar
  18. Pasin Manurangsi. Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis. In Proc. of ICALP, volume 80 of LIPIcs, pages 79:1-79:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  19. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(1-6):583-596, 1992. URL: http://dx.doi.org/10.1007/BF01758778.
  20. Hiroshi Nagamochi and Yoko Kamidoi. Minimum cost subpartitions in graphs. Information Processing Letters, 102(2):79-84, 2007. URL: http://dx.doi.org/10.1016/j.ipl.2006.11.011.
  21. J Naor and Yuval Rabani. Tree Packing and Approximating k-Cuts. In Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, volume 103, page 26. SIAM, 2001. Google Scholar
  22. H. Narayanan. The principal lattice of partitions of a submodular function. Linear Algebra and its Applications, 144:179-216, 1991. Google Scholar
  23. Kent Quanrud. Fast and Deterministic Approximations for k-Cut. CoRR, abs/1807.07143, 2018. URL: http://arxiv.org/abs/1807.07143.
  24. R Ravi and Amitabh Sinha. Approximating k-cuts using network strength as a lagrangean relaxation. European Journal of Operational Research, 186(1):77-90, 2008. Google Scholar
  25. Huzur Saran and Vijay V. Vazirani. Finding k-Cuts Within Twice the Optimal. SIAM J. Comput., 24(1):101-108, February 1995. Google Scholar
  26. Alexander Schrijver. Combinatorial optimization: polyhedra and efficiency, volume 24. Springer Science &Business Media, 2003. Google Scholar
  27. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. Journal of the ACM, 44(4):585-591, July 1997. URL: http://dx.doi.org/10.1145/263867.263872.
  28. Mikkel Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91-127, 2007. Google Scholar
  29. Mikkel Thorup. Minimum k-way cuts via deterministic greedy tree packing. In Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, pages 159-166. ACM, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact