The well-studied Tai mapping between two rooted labeled trees $T_1(V_1, E_1)$ and $T_2(V_2, E_2)$ defines a one-to-one mapping between nodes in $T_1$ and $T_2$ that preserves ancestor relationship. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete. In this work, we define an anti Tai mapping $M\subseteq V_1\times V_2$ as a binary relation between two unordered labeled trees such that any two $(x,y), (x', y')\in M$ violate ancestor relationship and thus cannot be part of the same Tai mapping, i.e. $(x\le x' \iff y\not \le y') \vee (x'\le x \iff y'\not \le y)$, given an ancestor order $x<x'$ meaning that $x$ is an ancestor of $x'$. Finding a maximum-weight anti Tai mapping arises in the cutting plane method for solving the maximum-weight Tai mapping problem via integer programming. We give an efficient polynomial-time algorithm for finding a maximum-weight anti Tai mapping for the case when one of the two trees is a path and further show how to extend this result in order to provide a polynomially computable lower bound on the optimal anti Tai mapping for two unordered labeled trees. The latter result stems from the special class of anti Tai mapping defined by the more restricted condition $x\sim x' \iff y\not\sim y'$, where $\sim$ denotes that two nodes belong to the same root-to-leaf path. For this class, we give an efficient algorithm that solves the problem directly on two unordered trees in $O(|V_1|^2|V_2|^2)$.
翻译:在两个已扎根标签的树 $T_1 (V_1, E_1) 和 $T_2(V_2, E_2) 之间仔细研究的Tai 映射定义了在$T_1美元和$T_2美元之间一对一的映射, 保存着前层关系。 对于未排序的树来说, 找到最大重量的Tai 映射的问题已知是 NP- 完成的。 在这项工作中, 我们定义了反Tai 映射$M\ subsete V_ 1\ times V_ 2美元 和 $Ta_ 2美元之间的双倍关系, 这意味着任何两个未排序的 $(x, y_ 2美元) 都违反了前层关系, 因此无法成为同一塔雅色图的一部分。 $(xxxxxxx) 最大重量 的映射结果在最高层层图中, 我们的Squal- deal dealmaisal 解算法中, 将一个最高级的DNA解算方法的解算为两个最高级的 。