Determining the consistency of resolved triplets and fan triplets

The R^+-F^+-Consistency problem takes as input two sets R⁺ and R^- of resolved triplets and two sets F⁺ and F^- of fan triplets, and asks for a distinctly leaf-labeled tree that contains all elements in R⁺ ⊂ F⁺ and no elements in R^- ⊂ F^- as embedded subtrees, if such a tree exists. This article presents a detailed characterization of how the computational complexity of the problem changes under various restrictions. Our main result is an efficient algorithm for dense inputs satisfying R^-=θ whose running time is linear in the size of the input and therefore optimal.