论文标题
近距离近距离距离的接近线性内核
A Near-Linear Kernel for Two-Parsimony Distance
论文作者
论文摘要
最大简约距离$ d _ {\ textrm {mp}}（t_1，t_2）$和有限状态的最大态度距离$ d _ {\ textrm {\ textrm {mp}}^t（t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t_1，t _ $ t $ a限制了字符中的状态数，在$ d _ {\ textrm {mp}}}}^t（t_1，t_2）$的情况下。虽然计算$ d _ {\ textrm {mp}}（t_1，t_2）$先前被证明是可与线性内核一起固定的参数，但没有以$ d _ {\ textrm {mp}}}}^t（t_1，t_1，t_2）$闻名的结果。在本文中，我们证明计算$ d _ {\ textrm {mp}}}^t（t_1，t_2）$是所有〜$ t $的固定参数。具体来说，我们证明此问题具有$ o（k \ lg k）$的内核，其中$ k = d _ {\ textrm {mp}}}^t（t_1，t_2）$。作为主要分析工具，我们介绍了腿部连接不相容的四重奏的概念，这可能引起了独立的兴趣。
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.
