MINIMUM K-CUT

• INSTANCE: Graph $G=\left(V,E\right)$, a weight function $w : E \rightarrow N$, and an integer $k\in[2..\vert V\vert$.

• SOLUTION: A partition of V into k disjoint sets $F=\{C_1,C_2,\ldots,C_k\}$.

• MEASURE: The sum of the weight of the edges between the disjoint sets, i.e.,
  
  $$\displaystyle\sum_{i=1}^{k-1}\displaystyle\sum_{j=i+1}^k \displaystyle\sum_{v_1\in C_i\atop v_2\in C_j} w(\{v_1,v_2\}).$$
  
  

  
  

• Good News: Approximable within $2-\frac{2}{k}$ [428].

• Comment: Solvable in polynomial time $O(\vert V\vert^{k^2})$ for fixed k [201]. If the sets in the partition are restricted to be of equal size, the problem is approximable within $\vert V\vert\cdot (k-1)/k$ [428]. If the sets in the partition are restricted to be of specified sizes and the weight function satisfies the triangle inequality, the problem is approximable within 3 for any fixed k [214]. The unweighted problem admits a PTAS if every vertex has degree $\Theta(\vert V\vert)$ [39].