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.

This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

Given an undirected graph G = (V, E) with an assignment of weights to the edges w: E → N and an integer

while minimizing For a fixed k, the problem is polynomial time solvable in

A simple greedy algorithm that achieves this approximation factor computes a minimum cut in each of the connected components and removes the lightest one.

Another algorithm achieving the same guarantee uses the Gomory–Hu tree representation of minimum cuts.

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