Minimum spanning forest, where each tree has the same number of vertices.

Question

Given a connected Graph $G(V,E)$ with weights $w\colon E\to\mathbb{N}$ and $|V|=kn$. How can I find the minimum spanning forest $T_1,T_2, \dots, T_n$ where each tree $T_i$ has exactly $k$ vertices?

I wonder if this problem is P or NP, I am particularly interested in the case $k=3$.

Answer 1

Note that trees of order 2 and 3 are stars. Therefore tree partition problem is star partition for $k \in \{\,2, 3\,\}$.

Two prominent special cases of Star Partition are the case $s = 1$ (finding a perfect matching) and the case $s = 2$ (finding a partition into connected triples). Perfect matchings ($s = 1$), of course, can be found in polynomial time. Partitions into connected triples (the case $s = 2$), however, are hard to find; this problem, denoted $P_3$-Partition, was proven to be NP-complete by Kirkpatrick and Hell. Partitioning Perfect Graphs into Stars

A weighted version of the tree decomposition problem includes all unweighted cases, therefore it is also NP-hard for $k = 3$. For $k = 2$ the minimum weight maximum matching problem is known to be solvable in polynomial time.