A 3-factor approximation algorithm for a Minimum Acyclic Agreement Forest on k rooted, binary phylogenetic trees

Molecular phylogenetics is a well-established field of research in biology wherein phylogenetic trees are analyzed to obtain insights into the evolutionary histories of organisms. Phylogenetic trees are leaf-labelled trees, where the leaves correspond to extant species (taxa), and the internal vertices represent ancestral species. The evolutionary history of a set of species can be explained by more than one phylogenetic tree, giving rise to the problem of comparing phylogenetic trees for similarity. Various distance metrics, like the subtree prune-and-regraft (SPR), tree bisection reconnection (TBR) and nearest neighbour interchange (NNI) have been proposed to capture this similarity. The distance between two phylogenetic trees can also be measured by the size of a Maximum Agreement Forest (MAF) on these trees, as it has been shown that the rooted subtree prune-and-regraft distance is 1 less than the size of a MAF. Thus, the smaller this size, the greater is the similarity between the two trees. Since computing a MAF of minimum size is an NP-hard problem, researchers have turned their attention to computing MAFs that approximate the minimum. Recently, it has been shown that the MAF on k( ≥ 2) trees can be approximated to within a factor of 8. In this paper, we improve this ratio to 3