Optimal evolutionary tree comparison by sparse dynamic programming

In computational biology one is often interested in finding the concensus between different evolutionary trees for the same set of species. A popular formalizations is the Maximum Agreement Subtree Problem (MAST) defined as follows: given a set A and two rooted trees 𝒯₀ and 𝒯₁ leaf-labeled by the elements of A, find a maximum cardinality subset B of A such that the restrictions of 𝒯₀ and 𝒯₁ to B are topologically isomorphic. Polynomial time solutions exist, but they rely on a dynamic program with Θ(n²) nodes-and Θ(n²) running time. We sparsify this dynamic program and show that MAST is equivalent to Unary Weighted Bipartite Matching (UWBM) modulo an O(nc^{√(log n}) additive overhead. Applying the best bound for UWBM, we get an O(n^1.5 log n) algorithm for MAST. From our sparsification follows an O(nc^{√(log n})) time algorithm for the special case of bounded degrees. Also here the best previous bound was Θ(n²)