Convex recolorings of strings and trees: Definitions, hardness results and algorithms
Convex recolorings of strings and trees: Definitions, hardness results and algorithms
复制标题
DOI：
10.1016/j.jcss.2007.10.003
复制
发表时间：
2008-08-01
影响因子：
1.1
通讯作者：
Snir, Sagi
中科院分区：
文献类型：
--
作者：
Moran, Shlomo;Snir, Sagi
一棵树的着色是凸的，如果属于任何颜色的顶点诱导一个连通子树;一个部分着色（它将颜色分配给一些顶点）是凸的，如果它可以被完成为一个凸（全）着色。树的凸着色出现在遗传学、语言学等领域，例如，在一个实施例中，一个完美的系统树是指每一个性状的状态都诱导出一个凸着色的树.当一个树的着色不是凸的时，人们希望知道它离凸着色“有多远”，什么是“最接近”它的凸着色.本文研究了这个距离的一个自然定义--邻接距离，这是使着色凸所需的顶点处的颜色变化的最小数目。我们发现，找到这个距离是NP难的，即使是一个彩色字符串（路径），并为其他一些有趣的变种的问题。在积极的一面，我们提出了一些自然的概括下，这个概念的计算的包围距离的算法：第一个概括是均匀加权模型，其中每个顶点有一个权重，这是改变其颜色的成本。另一种是非均匀模型，其中顶点v用颜色d着色的成本是任意非负数cost（v，d）。我们的第一个算法找到最佳的凸矩阵的字符串和有界度树下的非均匀模型的时间，对于任何固定数量的颜色，是线性的输入大小。接下来，我们改进了这些算法，使统一模型在时间上运行，对于固定数量的坏颜色，这些颜色在某种自然意义上违反了凸性。最后，我们将上述结果推广到无界度的树。(c)2008年爱思唯尔公司All rights reserved.
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 colorings of trees arise in areas such as phylogenetics, linguistics, etc., e.g., a perfect phylogenetic tree is one in which the states of each character induce a convex coloring of the tree.When a coloring of a tree is not convex, it is desirable to know "how far" it is from a convex one, and what are the convex colorings which are "closest" to it. In this paper we study a natural definition of this distance-the recoloring distance, which is the minimal number of color changes at the vertices needed to make the coloring convex. We show that finding this distance is NP-hard even for a colored string (a path), and for some other interesting variants of the problem. In the positive side, we present algorithms for computing the recoloring distance under some natural generalizations of this concept: the first generalization is the uniform weighted model, where each vertex has a weight which is the cost of changing its color. The other is the non-uniform model, in which the cost of coloring a vertex v by a color d is an arbitrary non-negative number cost(v, d). Our first algorithms find optimal convex recolorings of strings and bounded degree trees under the non-uniform model in time which, for any fixed number of colors, is linear in the input size. Next we improve these algorithm for the uniform model to run in time which is linear in the input size for a fixed number of bad colors, which are colors which violate convexity in some natural sense. Finally, we generalize the above result to hold for trees of unbounded degree. (c) 2008 Elsevier Inc. All rights reserved.