Fixed-parameter Tractability of the Maximum Agreement Supertree Problem
Abstract
Given a ground set $L$ of labels and a collection of trees whose leaves are bijectively labelled by some elements of $L$, the Maximum Agreement Supertree problem (\pSMAST) is the following: find a tree $T$ on a largest label set $L' \subseteq L$ that homeomorphically contains every input tree restricted to $L'$. The problem finds applications in phylogenetics, databases and data mining. In this paper we focus on the parameterized complexity of this NP-hard problem. We consider different combinations of parameters for SMAST as well as particular cases, providing both FPT algorithms and intractability results.