Tatsuya AkutsuThis 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.

Human Genome Center, Institute of Medical Science, University of TokyoMagnús M. Halldórsson

Science Institute, University of Iceland, IS-107 Reykjavik, Iceland.

- Postscript file (Sep 22, 1997)