On the Approximation of Largest Common Subtrees and Largest Common Point Sets

Tatsuya Akutsu
Human Genome Center, Institute of Medical Science, University of Tokyo

Magnús M. Halldórsson
Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

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 can not be approximated within a factor of n^{1-epsilon} in polynomial time for any epsilon > 0 unless NP = 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.