Minimum k-cut

In mathematics, the minimum Template:Mvar-cut is a combinatorial optimization problem that requires finding a set of edges whose removal would partition the graph to at least Template:Mvar connected components. These edges are referred to as Template:Mvar-cut. The goal is to find the minimum-weight Template:Mvar-cut. This partitioning can have applications in VLSI design, data-mining, finite elements and communication in parallel computing.

Minimum Template:Mvar-cut for Template:Mvar $=2$ and $3$ respectively (cuts highlighted red)

Formal definition

Given an undirected graph Template:Math with an assignment of weights to the edges Template:Math and an integer $k\in \{2,3,\dots ,|V|\},$ partition Template:Mvar into Template:Mvar disjoint sets $F=\{C_1,C_2,\dots ,C_k\}$ while minimizing

$\sum _{i=1}^{k-1}\sum _{j=i+1}^k\sum _{\begin{array}{c}{v}_1\in C_i\\ v_2\in C_j\end{array}}w(\{v_1,v_2\}).$

For a fixed Template:Mvar, the problem is polynomial time solvable in $O(|V{|}^{k^2}).$ However, the problem is NP-complete if Template:Mvar is part of the input. It is also NP-complete if we specify Template:Mvar vertices and ask for the minimum Template:Mvar-cut which separates these vertices among each of the sets.

Approximations

Several approximation algorithms exist with an approximation of $2-\frac{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 Template:Math max flow computations. Another algorithm achieving the same guarantee uses the Gomory–Hu tree representation of minimum cuts. Constructing the Gomory–Hu tree requires Template:Math max flow computations, but the algorithm requires an overall Template:Math 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 Template:Math factor for every constant Template:Math, meaning that the aforementioned approximation algorithms are essentially tight for large Template:Mvar.

A variant of the problem asks for a minimum weight Template:Mvar-cut where the output partitions have pre-specified sizes. This problem variant is approximable to within a factor of 3 for any fixed Template:Mvar 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 Template:Mvar-cut problem is W[1]-hard parameterized by Template:Mvar, a parameterized approximation scheme can be obtained for this parameter.

See also

• Maximum cut
• Minimum cut

References

• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Citation
• Template:Cite conference
• Template:Cite conference