Minimum k-cut
In mathematics, the minimum k-cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least k connected components. These edges are referred to as k-cut. The goal is to find the minimum-weight k-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.
Formal definition
Given an undirected graph G = (V, E) with an assignment of weights to the edges w: E → N and an integer [math]\displaystyle{ k \in \{2,3, \ldots, |V|\}, }[/math] partition V into k disjoint sets [math]\displaystyle{ F = \{ C_1,C_2,\ldots,C_k \} }[/math] while minimizing
- [math]\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 \} ) }[/math]
For a fixed k, the problem is polynomial time solvable in [math]\displaystyle{ O \bigl(|V|^{k^2} \bigr). }[/math][1] However, the problem is 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 [math]\displaystyle{ 2-\tfrac 2 k. }[/math] A simple greedy algorithm that achieves this approximation factor computes a minimum cut in each of the connected components and removes the lightest 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 (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 complete graph that satisfies the triangle inequality.[7] More recently, 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
- ↑ G. Downey, Rodney; Estivill-Castro, Vladimir; Fellows, Michael; Prieto, Elena; Rosamund, Frances A. (2003-04-01). "Cutting Up Is Hard To Do: The Parameterised Complexity of k-Cut and Related Problems" (in en). Electronic Notes in Theoretical Computer Science. CATS'03, Computing: the Australasian Theory Symposium 78: 209–222. doi:10.1016/S1571-0661(04)81014-4. ISSN 1571-0661. https://www.sciencedirect.com/science/article/pii/S1571066104810144.
- ↑ Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "A Parameterized Approximation Scheme for Min $k$-Cut". SIAM Journal on Computing: FOCS20–205. doi:10.1137/20M1383197. ISSN 0097-5397. https://epubs.siam.org/doi/10.1137/20M1383197.
References
- Goldschmidt, O. (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, http://www.cc.gatech.edu/~vazirani/k-cut.ps
- 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", Algorithmica, pp. 198–207, http://www.math.tau.ac.il/~hassin/k_cut_00.pdf
- Comellas, Francesc; Sapena, Emili (2006), "A multiagent algorithm for graph partitioning. Lecture Notes in Comput. Sci.", Algorithmica 3907 (2): 279–285, doi:10.1007/s004530010013, ISSN 0302-9743, http://www-ma4.upc.es/~comellas/evocomnet06/CoSa06-EvoCOMNET06.html
- Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús (2000), "Minimum k-cut", A Compendium of NP Optimization Problems, http://www.csc.kth.se/~viggo/wwwcompendium/node90.html
- Fernandez de la Vega, W.; Karpinski, M. (2004). "Approximation schemes for Metric Bisection and partitioning". pp. 506–515. http://dl.acm.org/citation.cfm?id=982792.982864.
- Manurangsi, P. (2017). "Inapproximability of Maximum Edge Biclique, Maximum Balanced Biclique and Minimum k-Cut from the Small Set Expansion Hypothesis". pp. 79:1–79:14. doi:10.4230/LIPIcs.ICALP.2017.79.
 |  |
