Constructing a Tree from Homeomorphic Subtrees, with Applications to Computational Evolutionary Biology

We are given a set T = fT 1 ; T 2 ; : : : ; T k g of rooted binary trees, each T i leaf-labeled by a subset L(T i ) ae f1; 2; : : :; ng. If T is a tree on f1; 2; : : :; ng, we let TjL denote the subtree of T induced by the nodes of L and all their ancestors. The consensus tree problem asks whether there exists a tree T such that for every i, T jL(T i ) is homeomorphic to T i . We present algorithms which test if a given set of trees has a consensus tree and if so, construct one. The deterministic algorithm takes time minfO(mn 1=2 ); O(m + n 2 log n)g, where m = P i jT i j and uses linear space. The randomized algorithm takes time O(m log 3 n) and uses linear space. The previous best for this problem was an 1981 O(mn) algorithm by Aho et al. Our faster deterministic algorithm uses a new efficient algorithm for the following interesting dynamic graph problem: Given a graph G with n nodes and m edges and a sequence of b batches of one or more edge deletions, then after ea..