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 paper 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.