  Given a tree $T$ on $n$ vertices, and $k, b, s_1, \ldots, s_b \in N$, the
Tree Partitioning problem asks if at most $k$ edges can be removed from $T$ so
that the resulting components can be grouped into $b$ groups such that the
number of vertices in group $i$ is $s_i$, for $i =1, \ldots, b$. The case when
$s_1=\cdots =s_b =n/b$, referred to as the Balanced Tree Partitioning problem,
was shown to be NP-complete for trees of maximum degree at most 5, and the
complexity of the problem for trees of maximum degree 4 and 3 was posed as an
open question. The parameterized complexity of Balanced Tree Partitioning was
also posed as an open question in another work.
  In this paper, we answer both open questions negatively. We show that
Balanced Tree Partitioning (and hence, Tree Partitioning) is NP-complete for
trees of maximum degree 3, thus closing the door on the complexity of Balanced
Tree Partitioning, as the simple case when $T$ is a path is in P. In terms of
the parameterized complexity of the problems, we show that both Balanced Tree
Partitioning and Tree Partitioning are $W[1]$-complete. Finally, using a
compact representation of the solution space for an instance of the problem, we
present a dynamic programming algorithm for Tree Partitioning (and hence, for
Balanced Tree Partitioning) that runs in subexponential-time $2^{O(\sqrt{n})}$,
adding a natural problem to the list of problems that can be solved in
subexponential time.
