Minimum k-cut
In mathematics, the minimum k-cut is a
finite elements and communication in parallel computing
.
Formal definition
Given an
while minimizing
For a fixed k, the problem is
polynomial time
solvable in 
NP-complete if k is part of the input.[2] It is also NP-complete if we specify k vertices and ask for the minimum k-cut which separates these vertices among each of the sets.[3]
Approximations
Several
approximation algorithms
exist with an approximation of A simple 
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 (2 − ε) factor for every constant ε > 0,[6]
meaning that the aforementioned approximation algorithms are essentially tight for large 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
polynomial time approximation schemes (PTAS) were discovered for those problems.[8]
While the minimum k-cut problem is W[1]-hard parameterized by k,[9] a parameterized approximation scheme can be obtained for this parameter.[10]
See also
Notes
- ^ Goldschmidt & Hochbaum 1988.
- ^ Garey & Johnson 1979
- ^ [1], which cites [2]
- ^ Saran & Vazirani 1991.
- ^ Vazirani 2003, pp. 40–44.
- ^ Manurangsi 2017
- ^ Guttmann-Beck & Hassin 1999, pp. 198–207.
- ^ Fernandez de la Vega, Karpinski & Kenyon 2004
- ISSN 1571-0661.
- ISSN 0097-5397.
References
- 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
- 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, S2CID 25721784, archived from the originalon 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. .