Convex recoloring of leaf-colored trees

Abstract

A coloring of the leaves of a tree T is called convex, if it is possible to give each internal node a color, such that for each color, the set of nodes with that color forms a subtree of T. Motivated by a problem from phylogenetic reconstruction, we study the problem, when given a tree with a coloring of its leaves, to recolor as few as possible leaves to obtain a convex coloring. We present first a linear time algorithm for verifying whether or not a given leaf colored tree is convex colorable. Then, we give a number of preprocessing rules for reducing the size of the given tree or splitting it into two or more subtrees. Finally, we introduce a branching algorithm for solving the problem in 4OPT·n, where OPT is the optimal solution for solving the problem, and show that the problem is fixed parameter tractable.