MAXIMUM 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 $1/(1-1/k+2\ln k/k^2)$ [176] and [367].

• Bad News: APX-complete.

• Comment: The unweighted version is equivalent to MAXIMUM K-COLORABLE SUBGRAPH. Approximable within 1.21 for k=3, 1.18 for k=4, and 1.15 for k=5 [176]. Not approximable within 1+1/(34k) [286]. MAXIMUM K-SECTION, the problem with the additional constraint that the partition must cut the graph into sets of equal size, is approximable within $1/(1-1/k+c k^3)$ for some constant c>0 [19].

  The constrained variation in which the input is extended with a positive integer W, a vertex $v_0\in V$ and a subset S of V, and the problem is to find the 2-cut of weight at least W with the largest number of vertices from S on the same side as $v_0$, is not approximable within $\vert V\vert^{\varepsilon }$ for some $\varepsilon >0$ [476].