Algorithms for Combining Rooted Triplets into a Galled Phylogenetic Network

This paper considers the problem of determining whether a given set of rooted triplets can be merged without conflicts into a galled phylogenetic network and, if so, constructing such a network. When the input is dense, we solve the problem in O(||) time, which is optimal since the size of the input is Θ(||). In comparison, the previously fastest algorithm for this problem runs in O(||²) time. We also develop an optimal O(||)-time algorithm for enumerating all simple phylogenetic networks leaf-labeled by L that are consistent with , where L is the set of leaf labels in , which is used by our main algorithm. Next, we prove that the problem becomes NP-hard if extended to nondense inputs, even for the special case of simple phylogenetic networks. We also show that for every positive integer n, there exists some set of rooted triplets on n leaves such that any galled network can be consistent with at most 0.4883 · || of the rooted triplets in . 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 .