Minimum k-cut

Given an undirected graph G = (V, E) with an assignment of weights to the edges w: E → N and an integer k ∈ {2, 3, …, |V|}, partition V into k disjoint sets F = {C₁, C₂, …, C_k} while minimizing

${\displaystyle \sum _{i=1}^{k-1}\sum _{j=i+1}^{k}\sum _{\begin{smallmatrix}v_{1}\in C_{i}\\v_{2}\in C_{j}\end{smallmatrix}}w(\left\{v_{1},v_{2}\right\})}$

For a fixed k, the problem is polynomial time solvable in O(|V|^k2).[1] However, the problem is NP-complete if k is part of the input.[2] It is also NP-complete if we specify ${\displaystyle k}$ vertices and ask for the minimum ${\displaystyle k}$-cut which separates these vertices among each of the sets.[3]

Several approximation algorithms exist with an approximation of 2 − 2/k. A simple greedy algorithm that achieves this approximation factor computes a minimum cut in each of the connected components and removes the heaviest one. This algorithm requires a total of n − 1 max flow computations. Another algorithm achieving the same guarantee uses the Gomory–Hu tree representation of minimum cuts. Constructing the Gomory–Hu tree requires n − 1 max flow computations, but the algorithm requires an overall O(kn) max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm.[4][5] Moreover, under the Small Set Expansion Hypothesis (a conjecture closely related to the Unique Games Conjecture), the problem is NP-hard to approximate to within ${\displaystyle (2-\epsilon )}$ factor for every constant ${\displaystyle \epsilon >0}$,[6] meaning that the aforementioned approximation algorithms are essentially tight for large ${\displaystyle k}$.

A variant of the problem asks for a minimum weight k-cut where the output partitions have pre-specified sizes. This problem variant is approximable to within a factor of 3 for any fixed k if one restricts the graph to a metric space, meaning a complete graph that satisfies the triangle inequality.[7] More recently, polynomial time approximation schemes (PTAS) were discovered for those problems.[8]

• Maximum cut
• Minimum cut

• Goldschmidt, O.; Hochbaum, D. S. (1988), Proc. 29th Ann. IEEE Symp. on Foundations of Comput. Sci., IEEE Computer Society, pp. 444–451
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 978-0-7167-1044-8
• Saran, H.; Vazirani, V. (1991), "Finding k-cuts within twice the optimal", Proc. 32nd Ann. IEEE Symp. on Foundations of Comput. Sci, IEEE Computer Society, pp. 743–751
• Vazirani, Vijay V. (2003), Approximation Algorithms, Berlin: Springer, ISBN 978-3-540-65367-7
• Guttmann-Beck, N.; Hassin, R. (1999), "Approximation algorithms for minimum k-cut" (PDF), Algorithmica, pp. 198–207
• Comellas, Francesc; Sapena, Emili (2006), "A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci.", Algorithmica, 3907 (2): 279–285, CiteSeerX 10.1.1.55.5697, doi:10.1007/s004530010013, ISSN 0302-9743, archived from the original on 2009-12-12
• Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (2000), "Minimum k-cut", A Compendium of NP Optimization Problems
• Fernandez de la Vega, W.; Karpinski, M.; Kenyon, C. (2004). "Approximation schemes for Metric Bisection and partitioning". Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete Algorithms. pp. 506–515.
• Manurangsi, P. (2017). "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis". 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017. pp. 79:1–79:14. doi:10.4230/LIPIcs.ICALP.2017.79.