### 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’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.

Original language | English |
---|---|

Title of host publication | Algorithms and Computation (Proceedings 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008) |

Editors | S.H. Hong, H. Nagamochi, T. Fukunaga |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 484-495 |

ISBN (Print) | 978-3-540-92181-3 |

DOIs | |

Publication status | Published - 2008 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 5369 |

ISSN (Print) | 0302-9743 |

## Fingerprint Dive into the research topics of 'New results on optimizing rooted triplets consistency'. Together they form a unique fingerprint.

## Cite this

Byrka, J., Guillemot, S., & Jansson, J. (2008). New results on optimizing rooted triplets consistency. In S. H. Hong, H. Nagamochi, & T. Fukunaga (Eds.),

*Algorithms and Computation (Proceedings 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008)*(pp. 484-495). (Lecture Notes in Computer Science; Vol. 5369). Berlin: Springer. https://doi.org/10.1007/978-3-540-92182-0_44