A near-linear kernel for bounded-state parsimony distance

The maximum parsimony distance dMP(T1, T2) and the bounded-state maximum parsimony distance dtMP(T1, T2) measure the difference between two phylogenetic trees T1, T2 in terms of the maximum difference between their parsimony scores for any character (with t a bound on the number of states in the character, in the case of dtMP(T1, T2)). While computing dMP(T1, T2) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for dtMP(T1, T2). In this paper, we prove that computing dtMP(T1, T2) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(k lgk), where k = dtMP(T1, T2). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.