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