- INSTANCE:
Connected graph
*G=(V, E)*, nonnegative vertex-weight function . - SOLUTION:
A partition
of
*V*into nonempty disjoint sets and such that the subgraphs of*G*induced by and are connected. - MEASURE:
Balance of the partition, i.e.,
,
where
.

*Good News:*Approximable within 4/3 [110].*Bad News:*Not approximable with an absolute error guarantee of for any [110].*Comment:*Variation in which the objective function is is approximable within [110].