We describe a kernel of size 9k−8 for the NP-hard problem of computing the Tree Bisection and Reconnection (TBR) distance k between two unrooted binary phylogenetic trees. To achieve this, we extend the existing portfolio of reduction rules with three novel new reduction rules. Two of the rules are based on the idea of topologically transforming the trees in a distance-preserving way in order to guarantee execution of earlier reduction rules. The third rule extends the local neighbourhood approach introduced in [20] to more global structures, allowing new situations to be identified when deletion of a leaf definitely reduces the TBR distance by one. The bound on the kernel size is tight up to an additive term. Our results also apply to the equivalent problem of computing a Maximum Agreement Forest (MAF) between two unrooted binary phylogenetic trees. We anticipate that our results will be more widely applicable for computing agreement-forest based dissimilarity measures.

Abstract. Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species (“taxa”), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [ Adv. Appl. Math., 84 (2017), pp. 34–46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity [Formula: see text], defined as the number of convex characters on [Formula: see text] in which each state appears on at least 2 taxa. We use this to give an algorithm with running time [Formula: see text], where [Formula: see text] is the golden ratio and [Formula: see text] is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by [Formula: see text] we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to [Formula: see text] and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees.

Given a set X of species, a phylogenetic tree is an unrooted binary tree whose leaves are bijectively labelled by X. Such trees can be used to show the way species evolve over time. One way of understanding how topologically different two phylogenetic trees are, is to construct a minimum-size agreement forest: a partition of X into the smallest number of blocks, such that the blocks induce homeomorphic, non-overlapping subtrees in both trees. This is called a maximum agreement forest. This comparison yields insight into commonalities and differences in the evolution of X across the two trees. Computing a maximum agreement forest is NP-hard [8]. In this work we study the problem on caterpillars, which are path-like phylogenetic trees. We will demonstrate that, even if we restrict the input to this highly restricted subclass, the problem remains NP-hard and is in fact APX-hard. Furthermore we show that for caterpillars two standard reduction rules well known in the literature yield a tight kernel of size at most 7k, compared to 15k for general trees [11].Finally we demonstrate that we can determine if two caterpillars have an agreement forest with at most k blocks in O⁎(2.49k) time, compared to O⁎(3k) for general trees [4], where O⁎(.) suppresses polynomial factors.