New reduction rules (and tight kernels) for computing the distance between phylogenetic trees

Given two phylogenetic (i.e. evolutionary) trees, the TBR-distance between them is the minimum number of "Tree Bisection and Reconnection" topological rearrangement moves required to transform one tree into another. This problem is NP-hard but was shown to be FPT in 2001 by Allen and Steel, who showed that polynomial-time reduction rules can be applied to reduce instances to size 28k, where k is the TBR distance. In this talk we show that the kernelization strategy proposed by Allen and Steel actually reduces the trees to size 15k-9, and that this is tight. The sharpened analysis is made possible by exploiting the equivalence of the TBR-distance problem to the problem of embedding the two trees parsimoniously into an undirected graph. Combining this equivalence with an older equivalence (that of "maximum agreement forests") then yields a whole suite of new polynomial-time reduction rules which further shrink the trees to size 11k-9. We conclude with some reflections on the wider significance of these insights for kernelization within phylogenetics.

Based on joint work with Dr. Simone Linz (Auckland).