A Near-Linear Kernel for Two-Parsimony Distance

2022/11/01 by Elise Deen, Leo van Iersel, Deen, Elise +9
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies

paper · pdf · doi:10.48550/arxiv.2211.00378

openalex publication_date 2022/11/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The maximum parsimony distance d_\textrmMP(T₁,T₂) and the bounded-state maximum parsimony distance d_\textrmMP^t(T₁,T₂) measure the difference between two phylogenetic trees T₁,T₂ 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_\textrmMP^t(T₁,T₂)). While computing d_\textrmMP(T₁, T₂) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for d_\textrmMP^t(T₁,T₂). In this paper, we prove that computing d_\textrmMP^t(T₁, T₂) 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_\textrmMP^t(T₁, T₂). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.

Related

• Maximum parsimony distance on phylogenetictrees: a linear kernel and constant factor approximation algorithm
• A strengthened bound on the number of states required to characterize maximum parsimony distance
• On the complexity of computing MP distance between binary phylogenetic trees
• On the Maximum Parsimony distance between phylogenetic trees
• A linear bound on the number of states in optimal convex characters for maximum parsimony distance