On the approximation of largest common subtrees and largest common point sets

This paper considers the approximability of the largest common subtree and the largest common point-set problems, which have applications in molecular biology. It is shown that the problems cannot be approximated within a factor of n(1-epsilon) in polynomial time for any epsilon > 0 Unless NP subset of or equal to ZPP, while a general search algorithm which approximates both problems within a factor of O(n/log n) is presented. For trees of bounded degree, an improved algorithm which approximates the largest common subtree within a factor of O(n/ log(2) n) is presented. Moreover, several variants of the largest common subtree problem are studied. (C) 2000 Elsevier Science B.V. All rights reserved.