Finding smallest supertrees

Abstract

We consider the problem of constructing the smallest supertree of two trees, where a supertree is a tree in which each of the two input trees can be embedded. Due to the use of trees in a wide variety of application areas, supertrees are also applicable in many different ways. When each of the two trees contains partial information about a data set, such as the evolution of a set of species, the supertree corresponds to a structuring of the data in a manner consistent with both original trees. The size of a supertree of two trees can also be used to measure the similarity between two arrangements of data, whether images, documents, or RNA secondary structures.

When the embedding relation is subgraph isomorphism, the problem reduces to that of finding the largest common subtree. The case of topological embedding, however, requires new techniques and algorithms. We show how the problem can be solved both sequentially and in parallel, for both ordered and unordered trees. In particular, the topological embedding problem can be solved in time O(n ²) sequentially and in parallel time O(log³ n) for ordered trees, and in time O(n ^2.5 log n) sequentially and in randomized parallel time O(log³ n) for unordered trees.

Research supported by the Natural Sciences and Engineering Research Council of Canada and the Advanced Systems Institute.

Research supported by the Natural Sciences and Engineering Research Council of Canada and the Information Technology Research Centre.