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

[edit]

Given an undirected graph G = (V, E) with an assignment of weights to the edges w: EN and an integer partition V into k disjoint sets while minimizing

For a fixed k, the problem is polynomial time solvable in [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

[edit]

Several approximation algorithms exist with an approximation of 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

[edit]

Notes

[edit]
  1. ^ Goldschmidt & Hochbaum 1988.
  2. ^ Garey & Johnson 1979
  3. ^ [1], which cites [2]
  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

[edit]