Deep kernelization for phylogenetic discordance

Phylogenetics is the science of constructing and comparing evolutionary trees and networks. Kernelization is a rigorous form of algorithmic pre-processing whereby a computationally difficult problem is reduced in size to make it more tractable. It is a fundamental technique in the design of fixed parameter tractable algorithms. Strikingly, although otherwise an early adopter of techniques from fixed parameter tractability (most notably: branching algorithms), the field of phylogenetics has thus far only made limited use of kernelization. This is because in the last twenty years only a very limited number of reduction rules have been developed, whose theoretical performance is poorly understood and whose practical impact is mixed. Recently we broke this stalemate by identifying a suite of new, provably more powerful reduction rules for the popular maximum agreement forest problem, which quantifies the discordance (i.e. topological dissimilarity) of phylogenetic trees. We also completely characterized the limits of existing rules. These results suggest that a larger family of progressively more powerful, deeper reduction rules exists and is tantalisingly within reach. In this proposal we will investigate this family, identify its theoretical and practical limits and extend the new reduction rules to a range of other optimization problems occurring in phylogenetics. We anticipate that the aggressively reduced instances will also yield structural insights that help in the design of faster branching and exponential-time algorithms. In this way we hope to close the gap between kernelization and branching algorithms that exists in phylogenetics, yielding theoretical and practical advances in the field.