  Maximum parsimony distance is a measure used to quantify the dissimilarity of
two unrooted phylogenetic trees. It is NP-hard to compute, and very few
positive algorithmic results are known due to its complex combinatorial
structure. Here we address this shortcoming by showing that the problem is
fixed parameter tractable. We do this by establishing a linear kernel i.e.,
that after applying certain reduction rules the resulting instance has size
that is bounded by a linear function of the distance. As powerful corollaries
to this result we prove that the problem permits a polynomial-time
constant-factor approximation algorithm; that the treewidth of a natural
auxiliary graph structure encountered in phylogenetics is bounded by a function
of the distance; and that the distance is within a constant factor of the size
of a maximum agreement forest of the two trees, a well studied object in
phylogenetics.
