TY - JOUR

T1 - Lp relaxation and tree packing for minimum k-CUT

AU - Chekuri, Chandra

AU - Quanrud, Kent

AU - Xu, Chao

N1 - Funding Information:
\ast Received by the editors November 13, 2019; accepted for publication (in revised form) March 29, 2020; published electronically June 16, 2020. A preliminary version of this paper appeared in Proceedings of the Symposium on Simplicity in Algorithms (SOSA), 2019. https://doi.org/10.1137/19M1299359 Funding: This research was supported in part by NSF grant CCF-1526799. \dagger Department of Computer Science, University of Illinois, Urbana, IL 61801 (chekuri@illinois.edu). \ddagger Department of Computer Science, Purdue University, West Lafayette, IN 47907 (krq@purdue. edu). \S Grab, Bellevue, WA 98004 (the.chao.xu@gmail.com, https://chaoxuprime.com/).
Publisher Copyright:
Copyright © by SIAM. Unauthorized reproduction of this article is prohibited.

PY - 2020

Y1 - 2020

N2 - Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46-76] 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 [D. R. Karger, Random Sampling in Graph Optimization Problems, Ph.D. thesis, Stanford University, Stanford, CA, 1995, D. R. Karger and C. Stein, J. ACM, 43 (1996), pp. 601-640]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [M. Thorup, Minimum k-way cuts via deterministic greedy tree packing, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 159-166]. In this paper we revisit properties of an LP relaxation for k-Cut proposed by Naor and Rabani [Tree packing and approximating k-cuts, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 103, SIAM, Philadelphia, 2001, pp. 26-27], and analyzed in [C. Chekuri, S. Guha, and J. Naor, SIAM J. Discrete Math., 20 (2006), pp. 261-271]. 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 [Oper. Res. Lett., 26 (2000), pp. 99-105] and Ravi and Sinha [European J. Oper. Res., 186 (2008), pp. 77-90]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP.

AB - Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46-76] 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 [D. R. Karger, Random Sampling in Graph Optimization Problems, Ph.D. thesis, Stanford University, Stanford, CA, 1995, D. R. Karger and C. Stein, J. ACM, 43 (1996), pp. 601-640]. Thorup developed a fast deterministic algorithm for the minimum k-cut problem via greedy recursive tree packings [M. Thorup, Minimum k-way cuts via deterministic greedy tree packing, in Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, ACM, 2008, pp. 159-166]. In this paper we revisit properties of an LP relaxation for k-Cut proposed by Naor and Rabani [Tree packing and approximating k-cuts, in Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Vol. 103, SIAM, Philadelphia, 2001, pp. 26-27], and analyzed in [C. Chekuri, S. Guha, and J. Naor, SIAM J. Discrete Math., 20 (2006), pp. 261-271]. 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 [Oper. Res. Lett., 26 (2000), pp. 99-105] and Ravi and Sinha [European J. Oper. Res., 186 (2008), pp. 77-90]; it also shows that the idealized recursive tree packing considered by Thorup gives an optimum dual solution to the LP.

KW - Approximation

KW - K-cut

KW - Minimum cut

KW - Tree packing

UR - http://www.scopus.com/inward/record.url?scp=85092287022&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85092287022&partnerID=8YFLogxK

U2 - 10.1137/19M1299359

DO - 10.1137/19M1299359

M3 - Article

AN - SCOPUS:85092287022

SN - 0895-4801

VL - 34

SP - 1334

EP - 1353

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

IS - 2

ER -