Some approximation results for the
maximum agreement forest problem
Estela Maris Rodrigues, Marie-France Sagot and Yoshiko
Wakabayashi
in APPROX and RANDOM'01, Lecture Notes in Computer
Science,
vol. 2129, pages 159-169, Springer Verlag, 2001
There are various techniques for reconstructing phylogenetic trees
from data, and in this context the problem of determining how distant
two such trees are from each other arises naturally. Various metrics
(NNI, SPR, TBR) for measuring the distance between two phylogenies
have been defined. Another way of comparing two trees T and
U is to compute the so called maximum agreement forest
of these trees. Informally, the number of components of an agreement
forest tells how many edges need to be cut from each of T and
U so that the resulting forests agree, after performing some
forced edge contractions. This problem is known to be NP-hard. It was
introduced by Hein et al. (1997), who presented an
approximation algorithm for it, claimed to have approximation ratio 3.
We present here a 3-approximation algorithm for this problem and show
that the performance ratio of Hein's algorithm is 4.
Paper in postscript format
Back to the Publications page