Constructing evolutionary trees for species sets is a fundamental prob
lem in biology. Unfortunately, there is no single agreed upon method f
or this task, and many methods are in use. Current practice dictates t
hat trees be constructed using different methods and that the resultin
g trees should be compared for consensus. It has become necessary to a
utomate this process as the number of species under consideration has
grown. We study one formalization of the problem: the maximum agreemen
t-subtree (MAST) problem. The MAST problem is as follows: given a set
A and two rooted trees T-0 and T-1 leaf-labeled by the elements of A,
find a maximum-cardinality subset B of A such that the topological res
trictions of T-0 and T-1 to B are isomorphic. In this paper, we will s
how that this problem reduces to unary weighted bipartite matching (UW
BM) with an O(n(1+o(1))) additive overhead. We also show that UWBM red
uces linearly to MAST. Thus our algorithm is optimal unless UWBM can b
e solved in near linear time. The overall running time of our algorith
m is O(n(1.5)log n), improving on the previous best algorithm, which r
uns in O(n(2)). We also derive an O(nc(root log n))-time algorithm for
the case of bounded degrees, whereas the previously best algorithm ru
ns in O(n(2)), as in the unbounded case.