Anti Tai mapping for unordered labeled trees

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 [1]. For unordered trees the problem of finding a maximum-weight Tai mapping is known to be NP-complete [2]. In this work, we define an anti Tai mapping M subset of V(1 )x V-2 as a binary relation between two unordered labeled trees such that any two (x, y),(x ', y ') is an element of M violate ancestor relationship and thus cannot be part of the same Tai mapping, i.e. (x <= x ' double left right arrow y not less than or equal to y ') boolean OR (x ' <= x double left right arrow y ' not less than or equal to 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 mappings defined by the more restricted condition x similar to x ' double left right arrow y not similar to y ', where similar to denotes that two nodes belong to the same root-to-leaf path. For this class, we give an efficient algorithm that solves the problem exactly on two unordered trees in O(|V-1|(2)|V-2|(2)).

Automated summary

This paper studies the Tai mapping and anti Tai mapping problems between rooted labeled trees. For unordered trees, finding the maximum-weight Tai mapping is proven to be NP-complete. The paper provides an efficient algorithm for finding the maximum-weight anti Tai mapping and presents a polynomial computable lower bound for the optimal anti Tai mapping based on special conditions.