LP relaxation and tree packing for minimum k-cuts

Chandra Chekuri, Kent Quanrud, Chao Xu

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Karger used spanning tree packings [14] 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 [13, 15]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [29]. In this paper we revisit properties of an LP relaxation for k-cut proposed by Naor and Rabani [21], and analyzed in [3]. 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 α-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 [2] and Ravi and Sinha [24]; 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 [29].

Original languageEnglish (US)
Title of host publication2nd Symposium on Simplicity in Algorithms, SOSA 2019 - Co-located with the 30th ACM-SIAM Symposium on Discrete Algorithms, SODA 2019
EditorsJeremy T. Fineman, Michael Mitzenmacher
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959770996
StatePublished - Jan 2019
Event2nd Symposium on Simplicity in Algorithms, SOSA 2019 - San Diego, United States
Duration: Jan 8 2019Jan 9 2019

Publication series

NameOpenAccess Series in Informatics
ISSN (Print)2190-6807


Conference2nd Symposium on Simplicity in Algorithms, SOSA 2019
Country/TerritoryUnited States
CitySan Diego


  • K-cut
  • LP relaxation
  • Tree packing

ASJC Scopus subject areas

  • Geography, Planning and Development
  • Modeling and Simulation


Dive into the research topics of 'LP relaxation and tree packing for minimum k-cuts'. Together they form a unique fingerprint.

Cite this