A faster FPT algorithm for the maximum agreement forest problem. (English) Zbl 1148.68049

Hallett, Michael; McCartin, Catherine

Theory Comput. Syst. 41, No. 3, 539-550 (2007).

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