Resolving Unresolved Resolved and Unresolved Triplets Consistency Problems

The \(\mathcal {R}^{+-} \mathcal {F}^{+-}\) Consistency problem is a basic problem related to the construction of phylogenetic trees. Its input is two sets  \(R^{+}\) and  \(R^{-}\) of resolved triplets and two sets  \(F^{+}\) and  \(F^{-}\) of unresolved triplets (also known as fan triplets). The objective of the problem is to determine if there exists a phylogenetic tree that includes all elements in  \(R^{+} \cup F^{+}\) and excludes all elements in  \(R^{-} \cup F^{-}\) as embedded subtrees, and to construct such a tree if one exists. Jansson et al. [Journal of Computational Biology, 2018] cataloged the computational complexity of the problem under various restrictions, with four notable exceptions in which the output tree is required to be ternary, i.e., has degree at most three. Here, we resolve these four remaining cases by proving that for ternary trees: (i)  \(\mathcal {F}^{+}\) Consistency as well as \(\mathcal {R}^{+} \mathcal {F}^{+}\) Consistency are solvable in polynomial time; and (ii)  \(\mathcal {F}^{+-}\) Consistency and \(\mathcal {R}^{+} \mathcal {F}^{+-}\) Consistency are NP-hard. To obtain (i), we develop a novel way of expressing the triplets Consistency problem for ternary trees as a system of equations whose nontrivial solutions can be used to partition the leaf labels into subsets that label subtrees of the output tree. Result (ii) is obtained after observing some new equivalences between resolved triplets and fan triplets consistent with a given phylogenetic tree.