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 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

\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).[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  2/k. A simple greedy algorithm that achieves this approximation factor computes a minimum cut in each 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 GomoryHu 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]

If we restrict the graph to a metric space, meaning a complete graph that satisfies the triangle inequality, and enforce that the output partitions are each of pre-specified sizes, the problem is approximable to within a factor of  3 for any fixed k.[6] More recently, polynomial time approximation schemes (PTAS) were discovered for those problems.[7]

See also

Notes

  1. Goldschmidt & Hochbaum 1988.
  2. Garey & Johnson 1979
  3. , which cites
  4. Saran & Vazirani 1991.
  5. Vazirani 2003, pp. 4044.
  6. Guttmann-Beck & Hassin 1999, pp. 198207.
  7. Fernandez de la Vega, Karpinski & Kenyon 2004

References

This article is issued from Wikipedia - version of the Wednesday, March 30, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.