MINIMUM EDGE DELETION K-PARTITION

• INSTANCE: Graph $G=\left(V,E\right)$ and a weight function $w : E \rightarrow N$.
• SOLUTION: A k-partition, i.e., a color assignment $c: V\rightarrow [1..k]$.
• MEASURE: The weight of the monochromatic edges, i.e., $\sum\limits_{(v_1,v_2) \in E: c(v_1)=c(v_2)}w(v_1,v_2)$.

  
  

• Good News: Approximable within $\log\vert V\vert$ for k=2 [189] and within $\varepsilon \vert V\vert^2$ for k=3 and any $\varepsilon >0$ [286].
• Bad News: Not in APX[426].
• Comment: Not approximable within 1.058 for k=2 [242]. Not approximable within $O(\vert E\vert)$ for $k\ge 3$, even for graphs with $\vert E\vert=\Omega(\vert V\vert^{2-\varepsilon })$ for any $\varepsilon >0$ [286]. Approximable within 9/4 for planar graphs and k=2 [199]. If G is the complete graph and w is required to satisfy the triangle inequality, then the problem is called MINIMUM K-CLUSTERING SUM (see Network Design).