A Faster FPT Algorithm for the Maximum Agreement Forest Problem

摘要

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 F = {t_l,…, 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 [2]. Whereas the algorithm from [2] 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(·) is a low order polynomial.