@inproceedings{4e6565b7a2f34fe1a2bf3ecf535d90c8,

title = "New results on optimizing rooted triplets consistency",

abstract = "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 (MaxRTC) and the minimum rooted triplets inconsistency problem (MinRTI) in which the input is a set R of rooted triplets, and where the objectives are to find a largest cardinality subset of R which is consistent and a smallest cardinality subset of R whose removal from R results in a consistent set, respectively. We first show that a simple modification to Wu{\textquoteright}s Best-Pair-Merge-First heuristic [25] results in a bottom-up-based 3-approximation for MaxRTC. We then demonstrate how any approximation algorithm for MinRTI could be used to approximate MaxRTC, and thus obtain the first polynomial-time approximation algorithm for MaxRTC with approximation ratio smaller 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 tree is approximately one third, and then provide a deterministic construction of a triplet set having a similar property which is subsequently used to prove that both MaxRTC and MinRTI are NP-hard even if restricted to minimally dense instances. Finally, we prove that MinRTI cannot be approximated within a ratio of O(log n) in polynomial time, unless P = NP.",

author = "J. Byrka and S. Guillemot and J. Jansson",

year = "2008",

doi = "10.1007/978-3-540-92182-0_44",

language = "English",

isbn = "978-3-540-92181-3",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "484--495",

editor = "S.H. Hong and H. Nagamochi and T. Fukunaga",

booktitle = "Algorithms and Computation (Proceedings 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008)",

address = "Germany",

}