Next: MAXIMUM K-COLORABLE SUBGRAPH Up: Subgraphs and Supergraphs Previous: MAXIMUM PLANAR SUBGRAPH Index

### MINIMUM EDGE DELETION K-PARTITION

- INSTANCE: Graph and a weight function .

- SOLUTION: A k-partition, i.e., a color assignment .

- MEASURE: The weight of the monochromatic edges, i.e., .

- Good News: Approximable within for k=2 [177] and within for k=3 and any [271].

- Bad News: Not in APX[403].

- Comment: Not approximable within 1.058 for k=2 [226]. Not approximable within O(|E|) for , even for graphs with for any [271]. Approximable within 9/4 for planar graphs and k=2 [187].

  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).