Hispanopedia Wiki
Articulo de referencia

Minimum k -cut

Minimum k -cut for k = 2 {\displaystyle =2} and 3 {\displaystyle 3} respectively (cuts highlighted red) In mathematics, the minimum k -cut is a combinatorial optimization proble...

Hispanopedia WikiContenido en espanolLectura gratuita
Minimum k-cut for k=2{\displaystyle =2} and 3{\displaystyle 3} respectively (cuts highlighted red)

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 kconnected 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 graphG = (V, E) with an assignment of weights to the edges w: E→N and an integerk∈{2,3,…,|V|},{\displaystyle k\in \{2,3,\ldots ,|V|\},}partitionV into kdisjoint setsF={C1,C2,…,Ck}{\displaystyle F=\{C_{1},C_{2},\ldots ,C_{k}\}} while minimizing

∑i=1k−1 ∑j=i+1k∑v1∈Civ2∈Cjw({v1,v2}).{\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).{\displaystyle O{\bigl (}|V|^{k^{2}}{\bigr )}.}[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 2−2k.{\displaystyle 2-{\tfrac {2}{k}}.} 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− 1max 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

  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
  9. ↑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". Electronic Notes in Theoretical Computer Science. CATS'03, Computing: the Australasian Theory Symposium. 78: 209–222. doi:10.1016/S1571-0661(04)81014-4. hdl:10230/36518. ISSN 1571-0661.
  10. ↑Lokshtanov, Daniel; Saurabh, Saket; Surianarayanan, Vaishali (2022-04-25). "A Parameterized Approximation Scheme for Min $k$-Cut". SIAM Journal on Computing: FOCS20–205. arXiv:2005.00134. doi:10.1137/20M1383197. 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"(PDF), 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, S2CID 25721784, 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
  • Fernández de la Vega, W.; Karpinski, M.; Kenyon, C. (2004). "Esquemas de aproximación para la bisección y partición métrica" . Actas del decimoquinto simposio anual ACM-SIAM sobre algoritmos discretos . págs. 506–515 . 
  • Manurangsi, P. (2017). "Inaproximabilidad de la biclique de aristas máxima, la biclique equilibrada máxima y el k-corte mínimo a partir de la hipótesis de expansión de conjuntos pequeños". 44.º Coloquio Internacional sobre Autómatas, Lenguajes y Programación, ICALP 2017. pp.  79:1–79:14. doi : 10.4230/LIPIcs.ICALP.2017.79 .