An efficient algorithm for the rooted triplet distance between galled trees

The previous fastest algorithm for computing the rooted triplet distance between two input galled trees (i.e., phylogenetic networks whose cycles are vertex-disjoint) runs in time, where n is the cardinality of the leaf label set. In this article, we present an-Time solution. Our strategy is to transform the input so that the answer can be obtained by applying an existing-Time algorithm for the simpler case of two phylogenetic trees a constant number of times. The new algorithm has been implemented, and applying it to pairs of randomly generated galled trees with up to leaves confirms that it is fast in practice.