Kernel and fast algorithm for dense triplet inconsistency

S. Guillemot, M. Mnich

Research output: Contribution to journalArticleAcademicpeer-review

6 Citations (Scopus)


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(k^2) labels, and a subexponential fixed-parameter algorithm running in time O(|L|^4)+2^{O(k^{1/3}logk)}.
Original languageEnglish
Pages (from-to)134-143
JournalTheoretical Computer Science
Publication statusPublished - 2013


Dive into the research topics of 'Kernel and fast algorithm for dense triplet inconsistency'. Together they form a unique fingerprint.

Cite this