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 VLSIdesign, data-mining, finite elements and communication in parallel computing.
Formal definition
Given an undirected graphG = with an assignment of weights to the edges w: E → N and an integerk ∈ , partition V into k disjoint sets F = while minimizing For a fixed k, the problem is polynomial time solvable in O. However, the problem is NP-complete if k is part of the input. It is also NP-complete if we specify vertices and ask for the minimum -cut which separates these vertices among each of the sets.
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 treerepresentation of minimum cuts. Constructing the Gomory-Hu tree requires n − 1 max flow computations, but the algorithm requires an overall O max flow computations. Yet, it is easier to analyze the approximation factor of the second algorithm. Moreover, under the Small Set Expansion Hypothesis, the problem is NP-hard to approximate to within factor for every constant, meaning that the aforementioned approximation algorithms are essentially tight for large. A variant of the problem asks for a minimum weightk-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. More recently, polynomial time approximation schemes were discovered for those problems.
