# zbMATH — the first resource for mathematics

A faster FPT algorithm for the maximum agreement forest problem. (English) Zbl 1148.68049
Summary: Given two unrooted, binary trees, $$T_{1}$$ and $$T_{2}$$, leaf labelled bijectively by a set of species $$L$$, the Maximum Agreement Forest (MAF) problem asks to find a minimum cardinality collection $$\mathcal F = \{t_{1},\ldots, t_{k}\}$$ of phylogenetic trees where each element of $$F$$ is a subtree of both $$T_{1}$$ and $$T_{2}$$, the elements of $$F$$ are pairwise disjoint, and the leaf labels for the elements of $$F$$ partition the leaf label set $$L$$. We give an efficient Fixed-Parameter Tractable (FPT) algorithm for the MAF problem, significantly improving on an FPT algorithm given in [B. Allen and M. Steel, Ann. Comb. 5, No. 1, 1–15 (2001; Zbl 0978.05023)]. Whereas the algorithm from [loc. cit.] has a running time of $$O(k^{3k}) + p(|L|)$$, our algorithm runs in time $$O(4^{k} k^{5}) + p(|L|)$$, where $$k$$ bounds the size of the agreement forest and $$p(\cdot)$$ is a low order polynomial.

##### MSC:
 68W05 Nonnumerical algorithms 05C05 Trees 05C85 Graph algorithms (graph-theoretic aspects) 68Q25 Analysis of algorithms and problem complexity 68R10 Graph theory (including graph drawing) in computer science 92D15 Problems related to evolution
Full Text: