A simple 4-approximation algorithm for maximum agreement forests on multiple unrooted binary trees

Maximum agreement forests have been used as a measure of dissimilarity of two or more phylogenetic trees on a given set of taxa. An agreement forest is a set of trees that can be obtained from each of the input trees by deleting edges and suppressing degree-2 vertices. A maximum agreement forest is such a forest with the minimum number of components. We present a simple 4-approximation algorithm for computing a maximum agreement forest of multiple unrooted binary trees. This algorithm applies LP rounding to an extension of a recent ILP formulation of the maximum agreement forest problem on two trees by Van Wersch et al. [13] . We achieve the same approximation ratio as the algorithm by Chen et al. [3] , but our algorithm is extremely simple. We also prove that no algorithm based on the ILP formulation by Van Wersch et al. can achieve an approximation ratio of 4 − ε , for any ε > 0 , even on two trees. To this end, we prove that the integrality gap of the ILP approaches 4 as the size of the two input trees grows. • A simple 4-approximation algorithm for computing maximum agreement forests for multiple unrooted phylogenetic trees. • Use of LP rounding and a relatively new ILP formulation to achieve results. • Proof that 4-approximation is the best obtainable via this ILP formulation, even for two trees.