A Kernel for the Maximum Agreement Forest Problem on Multiple Binary Phylogenetic Trees

Abstract

The maximum agreement forest (MAF) problem in phylogenetics takes as input a set $t \geq 2$ of binary phylogenetic trees $\mathcal T$ on the same set of taxa $X$. It asks for a partition of $X$ into the smallest number of blocks such that the subtrees induced by these blocks are disjoint and have common topology across all the trees in $\mathcal T$. We produce a modified version of the well-known chain reduction rule in order to prove that after exhaustive application of reduction rules each tree has  $O( t \cdot r \cdot k )$ leaves, where $k$ is the natural parameter (the number of blocks) and $r=\min\{\max\{k, 3\}, t+1\}$. We prove this bound for both the unrooted and rooted version of the problem, and demonstrate that the bound $r$, the length to which common chains are truncated, is tight. Our results constitute the first kernels for MAF in the $t>2$ regime.