  The maximum parsimony distance $d_{\textrm{MP}}(T_1,T_2)$ and the
bounded-state maximum parsimony distance $d_{\textrm{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_{\textrm{MP}}^t(T_1,T_2)$). While computing $d_{\textrm{MP}}(T_1, T_2)$ was
previously shown to be fixed-parameter tractable with a linear kernel, no such
result was known for $d_{\textrm{MP}}^t(T_1,T_2)$. In this paper, we prove that
computing $d_{\textrm{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_{\textrm{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.
