The Complexity of Constructing Evolutionary Trees Using Experiments

  • Gerth Stølting Brodal
  • Rolf Fagerberg
  • Christian N. S. Pedersen
  • Anna Östlin


We present tight upper and lower bounds for the problem of constructing evolutionary trees in the experiment model. We describe an algorithm which constructs an evolutionary tree of n species in time O(n d logd n) using at most n |d/2| (log2|d/2|−1 n + O(1)) experiments for d > 2, and
at most n(log n + O(1)) experiments for d = 2, where d is the degree of the tree. This improves the previous best upper bound by a factor Theta(log d). For d = 2 the previously best algorithm with running time O(n log n) had a bound of 4n log n on the number of experiments. By an explicit adversary argument, we show an
Omega(nd logd n) lower bound, matching our upper bounds and improving the previous best lower bound
by a factor Theta(logd n). Central to our algorithm is the construction and maintenance of separator trees of small height. We present how to maintain separator trees with height log n + O(1) under the insertion of new nodes in amortized time O(log n). Part of our dynamic algorithm is an algorithm for computing a centroid tree in optimal time O(n).

Keywords: Evolutionary trees, Experiment model, Separator trees, Centroid tree, Lower bounds

How to Cite
Brodal, G., Fagerberg, R., Pedersen, C., & Östlin, A. (2001). The Complexity of Constructing Evolutionary Trees Using Experiments. BRICS Report Series, 8(1).