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 k ∈ {2, 3, …, |V|}, partition V into k disjoint sets F = {C1, C2, …, Ck} while minimizing

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 vertices and ask for the minimum -cut which separates these vertices among each of the sets.[3]

Approximations

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 factor for every constant ,[6] meaning that the aforementioned approximation algorithms are essentially tight for large .

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]

gollark: I'm not actually old enough to vote, and in any case the only party which appears to actually care about this is the Liberal Democrats, who are not doing well in Parliament.
gollark: Yes. Democracy in action.
gollark: I complained to my MP when the government did some particularly egregious thing... complaining about end to end encryption on the news again, or something... and got a response back... from some random minister... by letter... two weeks later... which did not address anything I said and was related only in that my email and their response were both vaguely about encryption.
gollark: Er, act. Not bill.
gollark: *cough*investigatorypowersbill*cough*

See also

Notes
  1. Goldschmidt & Hochbaum 1988.
  2. Garey & Johnson 1979
  3. , which cites
  4. Saran & Vazirani 1991.
  5. Vazirani 2003, pp. 40–44.
  6. Manurangsi 2017
  7. Guttmann-Beck & Hassin 1999, pp. 198–207.
  8. Fernandez de la Vega, Karpinski & Kenyon 2004

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
  • 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.CS1 maint: ref=harv (link)
  • 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.CS1 maint: ref=harv (link)
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.