A Unifying View on Approximation and FPT of Agreement Forests

Authors: 

Chris Whidden
Norbert Zeh

Author Addresses: 

Faculty of Computer Science
Dalhousie University
6050 University Ave.
PO Box 15000
Halifax, Nova Scotia, Canada
B3H 4R2

Abstract: 

We provide a unifying view on the structure of different types of agreement forests using a "shifting lemma'' proved by Bordewich et al. We consider rooted and unrooted maximum agreement forests (MAF's) and rooted maximum acyclic agreement forests (MAAF's). Their sizes are known to respectively correspond to the subtree prune and regraft distance between two rooted phylogenies, the tree bisection and reconnection distance between two unrooted phylogenies, and the hybridization number of two rooted phylogenies. With the exception of approximation of rooted MAF, we obtain improved approximation and fixed-parameter algorithms for the sizes of all of the above types of agreement forests, most of which are substantial improvements over the best previous results. To the best of our knowledge, our 3-approximation algorithm for MAAF size is the first approximation result for MAAF. For rooted MAF size, we obtain an alternative and, in our opinion, simpler correctness proof for the 3-approximation algorithm by Rodrigues et al.

Tech Report Number: 
CS-2009-02
Report Date: 
June 15, 2009
AttachmentSize
PDF icon CS-2009-02.pdf559.38 KB