Agreement forests of caterpillar trees: complexity, kernelization and branching
share
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 comparison yields insight into commonalities and differences in the evolution of X across the two trees. Computing a smallest agreement forest is NP-hard (Hein, Jiang, Wang and Zhang, Discrete Applied Mathematics 71(1-3), 1996). 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 reductions rules well known in the literature yield a tight kernel of size at most 7k, compared to 15k for general trees (Kelk and Simone, SIAM Journal on Discrete Mathematics 33(3), 2019). Finally we demonstrate that we can determine if two caterpillars have an agreement forest with at most k blocks in O^*(2.49^k) time, compared to O^*(3^k) for general trees (Chen, Fan and Sze, Theoretical Computater Science 562, 2015), where O^*(.) suppresses polynomial factors.
READ FULL TEXT