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.

Given an undirected graph G = (V, E) with an assignment of weights to the edges w: E → N and an integer ${\displaystyle k\in \{2,3,\ldots ,|V|\},}$ partition V into k disjoint sets ${\displaystyle F=\{C_{1},C_{2},\ldots ,C_{k}\}}$ while minimizing

${\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 ${\displaystyle O{\bigl (}|V|^{k^{2}}{\bigr )}.}$¹ However, the problem is NP-complete if k is part of the input.² 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.³

Several approximation algorithms exist with an approximation of ${\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 − 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.⁴⁵ 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,⁶ 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.⁷ More recently, polynomial time approximation schemes (PTAS) were discovered for those problems.⁸

While the minimum k-cut problem is W[1]-hard parameterized by k,⁹ a parameterized approximation scheme can be obtained for this parameter.¹⁰