New results on optimizing rooted triplets consistency Original Research Article

A set of phylogenetic trees with overlapping leaf sets is consistent if it can be merged without conflicts into a supertree. In this paper, we study the polynomial-time approximability of two related optimization problems called the maximum rooted triplets consistency problem (image) and the minimum rooted triplets inconsistency problem (image) in which the input is a set image of rooted triplets, and where the objectives are to find a largest cardinality subset of image which is consistent and a smallest cardinality subset of image whose removal from image results in a consistent set, respectively. We first show that a simple modification to Wu’s Best-Pair-Merge-First heuristic Wu (2004) results in a bottom-up-based 3-approximation algorithm for image. We then demonstrate how any approximation algorithm for image could be used to approximate image, and thus obtain the first polynomial-time approximation algorithm for image with approximation ratio less than 3. Next, we prove that for a set of rooted triplets generated under a uniform random model, the maximum fraction of triplets which can be consistent with any phylogenetic tree is approximately one third. We then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both image and image are image-hard even if restricted to minimally dense instances. Finally, we prove that unless image, image cannot be approximated within a ratio of image for some constant image in polynomial time, where image denotes the cardinality of the leaf label set of image.