Algorithms for combining rooted triplets into a galled phylogenetic network

Abstract

This paper considers the problem of determining whether a given set T of rooted triplets can be merged without conflicts into a galled phylogenetic network, and if so, constructing such a network. When the input T is dense, we solve the problem in O(|T|) time, which is optimal since the size of the input is Θ(|T|). In comparison, the previously fastest algorithm for this problem runs in O(|T| 2) time. Next, we prove that the problem becomes NP-hard if extended to non-dense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set T of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883· |T| of the rooted triplets in T. On the other hand, we provide a polynomial-time approximation algorithm that always outputs a galled network consistent with at least a factor of 5/12 (> 0.4166) of the rooted triplets in T.