# Parameterized Algorithms in Bioinformatics: An Overview
## 5 Phylogenetics
### Combining and Comparing Phylogenies
#### 5.2.2 Consensus by Removing Taxa  
In many sciences, the most interesting knowledge can be gained by looking more closely to the non-conforming data points. In this spirit, biologists are particularly interested in taxa causing non-compatibility, that is, whose removal allows for an agreement supertree. In the spirit of parsimony, we are thus tempted to ask for a smallest number of taxa to remove from the input trees such that an agreement supertree exists.  
Maximum Agreement Supertree (MASP (also SMAST or MLI in the literature)) [noitemsep] **Input:** trees \(T_{1},T_{2},\ldots,T_{t}\) on \(\mathcal{X}_{1},\mathcal{X}_{2},\ldots\), respectively, and some \(k\in\mathbb{N}\)  
**Question:** Is there a tree \(T^{*}\) on \(\mathcal{X}\) such that \(|\bigcup_{i}\mathcal{X}_{i}\setminus\mathcal{X}|\leq k\) and \(\forall_{i}\;T^{*}|_{\mathcal{X}_{i}}=T_{i}|_{\mathcal{X}}\)?  
**Results.** While MASP can be solved in \(O(n^{1.5})\) time for two rooted trees [166; 167; 168] (\(n\) denoting the total number of labels in the input), it is NP-hard for \(t>2\), even if all \(T_{i}\) are triplets [166; 169], and the NP-hardness persists for fixed \(t\)[166] (but large trees). [PERSON] and [PERSON] [170] showed that, on dense, binary, rooted inputs, MASP can be solved in \(O(4^{k}n^{3})\) and \(O(3.12^{k}+n^{4})\) time by reduction to 4-Hitting Set. They further improved an \(O(t(2n^{2})^{3t^{2}})\)-time algorithm of [PERSON] et al. [166] for binary \(T_{i}\) to \(O((8n)^{t})\) time [170], which was subsequently improved to \(O((6n)^{t})\) time by [PERSON] and [PERSON] [171]. The latter also gave an \(O((t\Delta)^{t\Delta+3}(2n)^{t})\)-time algorithm for general rooted inputs (\(\Delta\)denoting the maximum out-degree among the input trees). MASP is W[2]-hard for \(k\), even if the input consists of rooted triplets [169], and W[1]-complete in the rooted case for the dual parameter \(n-k\), even if we add \(t\) to it [170]. On the positive side, the problem can be solved in \(O((2t)^{k}tn^{2})\) time for binary trees [170] which has been generalized to arbitrary trees by [PERSON] et al. [172]. For completeness, we want to point out that many of the results for MASP also hold for MASP's sister problem Maximum Compatible Supertree (MCSP), in which equality with the restricted agreement supertree \(T^{*}\) is relaxed to being a contraction of \(T^{*}\) (with the notable exception that MCSP can be solved in \(O(2^{2\Lambda}n^{t})\) time in both the rooted and unrooted case [171]).  
NotesThe special case of MASP in which \(\mathcal{X}_{1}=\mathcal{X}_{2}=\ldots\) is called Maximum Agreement Subtree (MAST) and has been studied extensively. While still NP-hard for \(t=3\) non-binary trees [173], MAST can be solved in \(O(kn^{3}+n^{\Delta})\)[157; 174], in which time we can also compute a \"kernel agreement subtree\", denoting the intersection of all leaf-sets of all optimal maximum agreement subtrees [175]. MAST is fixed-parameter tractable for \(k\) with parameterized algorithms running in time \(O(\min\{3^{k}tn,2.18^{k}+tn^{3}\})\)[176; 177; 178] (by reduction to 3-Hitting Set).  
More fine-grained versions of MAST that allow removal of different taxa from each \(T_{i}\) were introduced by [PERSON] et al. [179]. In Agreement Subtree by Leaf-Removal (AST-LR), the objective is to minimize _the total number \(q\)_ of removed leaves and, in AST-LR-\(d\), the objective is to minimize _the maximum number \(d\)_ of leaves that have to be removed from any of the trees. Both versions are NP-hard [179] but can be solved in \(O((4q-2)^{q}t^{2}n^{2})\) (AST-LR) and \(O(c^{d}d^{3d}(n^{3}+tn\log n))\) time for some constant \(c\) (AST-LR-\(d\)) [179; 180].  
[PERSON] et al. [181] considered MAST for multi-labeled trees showing that it remains NP-hard and can be solved in \(O^{*}((2n)^{t}k^{kt})\) time.  
Finally, [PERSON] et al. [141] showed that a \"maximum agreement sub_network_\" for two binary networks of level \(\ell_{1}\) and \(\ell_{2}\), respectively, can be computed in \(O^{*}(2^{\ell_{1}+\ell_{2}})\) time.