Technical Report CS-2003-13

Title: Convex Recoloring of Strings and Trees
Authors: Shlomo Moran and Sagi Snir
Abstract: A coloring of a tree is convex if the vertices that pertain to any color induce a connected subtree; a partial coloring (which assigns colors to some of the vertices) is convex if it can be completed to a convex (total) coloring. Convex coloring of trees arises in areas such as phylogenetics, linguistics, etc. eg, a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree. Research on perfect phylogeny is usually focused on finding a tree so that few predetermined partial colorings of its vertices are convex. When a coloring of a tree is not convex, it is desirable to know "how far" it is from a convex one. One common measure for this is based on the parsimony score, which is the number of edges whose endpoints have different colors. In this paper we study another natural measure for this distance: the minimal number of color changes at the vertices needed to make the coloring convex. This can be viewed as minimizing the number of ``exceptional vertices" w.r.t. to a closest convex coloring. We also study a similar measure which aims at minimizing the number of ``exceptional edges" w.r.t. a closest convex coloring. %(corresponding to edges with color changes that should be removed). We show that finding each of these distances is NP-hard even for strings. We then focus on the first measure and generalize it to weighted trees, and then to non-uniform coloring costs. In the positive side we present few algorithms for convex recoloring of strings of trees: First we present algorithms for optimal convex recolorings of strings and trees with non-uniform coloring costs, which for any fixed number of colors are linear in the input size. Then we present fixed parameter tractable algorithms and approximation algorithms for convex recolorings of weighted strings and trees.
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 2003
To the main CS technical reports page

Computer science department, Technion