Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

Viet Tung Hoang; Wing-Kin Sung

paper

Fixed Parameter Polynomial Time Algorithms for Maximum Agreement and Compatible Supertrees

arXiv:0802.2867

Abstract

Consider a set of labels $L$ and a set of trees ${\mathcal T} = \{{\mathcal T}^{(1), {\mathcal T}^{(2), ..., {\mathcal T}^{(k) \$ where each tree ${\mathcal T}^{(i) $i s d i s t in c tl y l e a f - l ab e l e d b y so m es u b se t o f$ L $. O n e f u n d am e n t a l p r o b l e mi s t o f in d t h e bi g g es tt r ee (d e n o t e d a ss u p er t r ee) t or e p r ese n t$ \mathcal T} $w hi c hminimi z es t h e d i s a g r ee m e n t s w i t h t h e t r ees in$ {\mathcal T} $u n d er cer t ain cr i t er ia . T hi s p r o b l e m f in d s a ppl i c a t i o n s in p h y l o g e n e t i cs, d a t aba se, an dd a t aminin g . I n t hi s p a p er, w e f oc u so n tw o p a r t i c u l a r s u p er t r ee p r o b l e m s, nam e l y, t h e ma x im u ma g r ee m e n t s u p er t r ee p r o b l e m (M A S P) an d t h e ma x im u m co m p a t ib l es u p er t r ee p r o b l e m (M C S P) . T h ese tw o p r o b l e m s a r e k n o w n t o b e N P - ha r df or$ k \geq 3 $. T hi s p a p er g i v es t h e f i r s tp o l y n o mia l t im e a l g or i t hm s f or b o t h M A S P an d M C S P w h e nb o t h$ k $an d t h e ma x im u m d e g r ee$ D$ of the trees are constant.