- 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 [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 for some constant*c>0*[19].The constrained variation in which the input is extended with a positive integer

*W*, a vertex 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 , is not approximable within for some [476].