An extended formulation of the convex recoloring problem on a tree

We introduce a strong extended formulation of the convex recoloring problem on a tree, which has an application in analyzing a phylogenetic tree. The extended formulation has only polynomial number of constraints, but dominates the conventional formulation and the exponentially many valid inequalities introduced by Campêlo et al. (Mathematical Programming, Published Online on March 4). We show that all valid inequalities introduced by Campêlo et al. can be derived from the extended formulation. The extended formulation solves all the problem instances attempted in Campêlo et al. and larger sized instances at the root node of the branch-and-bound tree without branching. The solution time using the extended formulation is much faster.