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

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$$.

• possibly of interest: case $k=2$ is the minimum-weight perfect matching problem, which can be solved in polynomial time, e.g. via the blossom algorithm Commented Aug 23, 2022 at 6:08

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.