A subexponential algorithm for the coloured tree partition problem

Given a tree of $n$ vertices and a list of feasible colours for each vertex, the \emph{Coloured Tree Partition Problem\/} (\emph{CTPP\/}) consists in partitioning the tree into $p$ vertex-disjoint subtrees of minimum total cost, and assigning to each subtree a different colour, which must be feasible for all of its vertices. The problem is strongly $\mathcal{NP}$-hard on general graphs, as well as on grid and bipartite graphs. This paper deals with the previously open case of tree graphs, showing that it is strongly $\mathcal{NP}$-complete to determine whether a feasible solution exists. It presents reduction, decomposition and bounding procedures to simplify the problem and an exact algorithm of $O( n \, p^{\log_{2}\left( a\sqrt{p-2} \right)} )$ complexity (with $a > 3\sqrt{2}$) for the special case in which a vertex of each subtree is given.