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.

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: DOI