  Given two rooted phylogenetic trees on the same set of taxa X, the Maximum
Agreement Forest problem (MAF) asks to find a forest that is, in a certain
sense, common to both trees and has a minimum number of components. The Maximum
Acyclic Agreement Forest problem (MAAF) has the additional restriction that the
components of the forest cannot have conflicting ancestral relations in the
input trees. There has been considerable interest in the special cases of these
problems in which the input trees are required to be binary. However, in
practice, phylogenetic trees are rarely binary, due to uncertainty about the
precise order of speciation events. Here, we show that the general, nonbinary
version of MAF has a polynomial-time 4-approximation and a fixed-parameter
tractable (exact) algorithm that runs in O(4^k poly(n)) time, where n = |X| and
k is the number of components of the agreement forest minus one. Moreover, we
show that a c-approximation algorithm for nonbinary MAF and a d-approximation
algorithm for the classical problem Directed Feedback Vertex Set (DFVS) can be
combined to yield a d(c+3)-approximation for nonbinary MAAF. The algorithms for
MAF have been implemented and made publicly available.
