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

  • 2
    $\begingroup$ 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 $\endgroup$
    – jacob
    Commented Aug 23, 2022 at 6:08

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


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .