New Results on Optimizing Rooted Triplets Consistency

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 ($\textsc{MaxRTC}$) and the minimum rooted triplets inconsistency problem ($\textsc{MinRTI}$) in which the input is a set $\mathcal{R}$ of rooted triplets, and where the objectives are to find a largest cardinality subset of $\mathcal{R}$ which is consistent and a smallest cardinality subset of $\mathcal{R}$ whose removal from $\mathcal{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 $\textsc{MaxRTC}$. We then demonstrate how any approximation algorithm for $\textsc{MinRTI}$ could be used to approximate $\textsc{MaxRTC}$, and thus obtain the first polynomial-time approximation algorithm for $\textsc{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 $\textsc{MaxRTC}$ and $\textsc{MinRTI}$ are NP-hard even if restricted to minimally dense instances. Finally, we prove that $\textsc{MinRTI}$ cannot be approximated within a ratio of Ω(logn) in polynomial time, unless P = NP.