- INSTANCE:
Graph
,
a weight function
,
and an
integer .
- SOLUTION:
A partition of
*V*into*k*disjoint sets . - MEASURE:
The sum of the weight of the edges between the disjoint sets, i.e.,

*Good News:*Approximable within [428].*Comment:*Solvable in polynomial time for fixed*k*[201]. If the sets in the partition are restricted to be of equal size, the problem is approximable within [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 [39].