A Near-Linear Kernel for Two-Parsimony Distance

Abstract

The maximum parsimony distance $d_{\text{MP}}(T_1,T_2)$ and the bounded-state maximum parsimony distance $d_{\text{MP}}^t(T_1,T_2)$ measure the difference between two phylogenetic trees $T_1,T_2$ 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 $d_{\text{MP}}^t(T_1,T_2)$). While computing $d_{\text{MP}}(T_1,T_2)$ was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for $d_{\text{MP}}^t(T_1,T_2)$. In this paper, we prove that computing $d_{\text{MP}}^t(T_1,T_2)$ is fixed-parameter tractable for all~$t$. Specifically, we prove that this problem has a kernel of size $O(k\lg k)$, where $k=d_{\text{MP}}^t(T_1,T_2)$. As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.