4
$\begingroup$

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

$\endgroup$
1
  • 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

6
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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