Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

Abstract

Consider a set of labels $L$ and a set of trees ${mathcal T} = {
   {mathcal T}^{(1), {mathcal T}^{(2), ldots, {mathcal T}^{(k) $
   where each tree ${mathcal T}^{(i)$ is distinctly leaf-labeled by
   some subset of $L$.  One fundamental problem is to find the biggest
   tree (denoted as supertree) to represent $mathcal T}$ which
   minimizes the disagreements with the trees in ${mathcal T}$ under
   certain criteria.  This problem finds applications in
   phylogenetics, database, and data mining.  In this paper, we focus
   on two particular supertree problems, namely, the maximum agreement
   supertree problem (MASP) and the maximum compatible supertree
   problem (MCSP).  These two problems are known to be NP-hard for $k
   geq 3$.  This paper gives the first polynomial time algorithms for
   both MASP and MCSP when both $k$ and the maximum degree $D$ of the
   trees are constant.