MINIMUM K-CAPACITATED TREE PARTITION

• INSTANCE: Graph $G=\left(V,E\right)$, and a weight function $w : E \rightarrow N$.
• SOLUTION: A k-capacitated tree partition of G, i.e., a collection of vertex disjoint subsets $E_1, \ldots, E_m$ of E such that, for each i, the subgraph induced by $E_i$ is a tree of at least k vertices.
• MEASURE: The weight of the partition, i.e., $\sum_i\sum_{e\in E_i} w(e)$.

  
  

• Good News: Approximable within $2-1/\vert V\vert$ [197].
• 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/\vert V\vert)$. Similar results hold for the corresponding cycle and path partitioning problems with the triangle inequality [197]. Variation in which the trees must contain exactly k vertices and the objective is to minimize $\max_i\sum_{e\in E_i} w(e)$ is not in APX, but if the triangle inequality is satisfied it is approximable within $2\vert V\vert/k-1$ [211]. The variation in which the number m of trees is fixed, the trees' sizes are exactly specified, and the triangle inequality is satisfied is approximable within 2p-1 [212].