Kernel and fast algorithm for dense triplet inconsistency

We study the parameterized complexity of inferring supertrees from sets of rooted triplets, an important problem in phylogenetics. For a set L of labels and a dense set T of triplets distinctly leaf-labeled by 3-subsets of L, we seek a tree distinctly leaf-labeled by L and containing all but at most k triplets from  T as homeomorphic subtree. Our results are the first polynomial kernel for this problem, with O(k2) labels, and a subexponential fixed-parameter algorithm running in time O(∣L∣4)+2O(k1/3logk).