S
OLUTION
:
A
k
-capacitated tree partition of
G
, i.e., a collection of vertex disjoint
subsets
of
E
such that, for each
i
, the subgraph induced
by
is a tree of at least
k
vertices.
Comment:
The variation in which the trees must contain exactly
k
vertices and the
triangle inequality is satisfied is approximable within
4(1-1/k)(1-1/|V|)
.
Similar results hold for the corresponding cycle and path partitioning problems
with the triangle inequality [
134
].
, and a weight function
.
of
E
such that, for each
i
, the subgraph induced
by
is a tree of at least
k
vertices.
.