Quadratic kernelization for convex recoloring of trees

The Convex Recoloring (CR) problem measures how far a tree of characters differs from exhibiting a so-called "perfect phylogeny". For an input consisting of a vertex-colored tree T, the problem is to determine whether recoloring at most k vertices can achieve a convex coloring, meaning by this a coloring where each color class induces a subtree. The problem was introduced by Moran and Snir (J. Comput. Syst. Sci. 73:1078-1089, 2007; J. Comput. Syst. Sci. 74:850-869, 2008) who showed that CR is NP-hard, and described a search-tree based FPT algorithm with a running time of O(k(k/log k) (k) n (4)). The Moran and Snir result did not provide any nontrivial kernelization. In this paper, we show that CR has a kernel of size O(k (2))