A subexponential algorithm for the coloured tree partition problem

Given a tree of nn vertices and a list of feasible colours for each vertex, the coloured tree partition problem (CTPP  ) consists in partitioning the tree into pp 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 NPNP-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 NPNP-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(nplog2(ap-2)) complexity (with a>32) for the special case in which a vertex of each subtree is given.