A near-linear kernel for bounded-state parsimony distance

Deen, Elise; van Iersel, L.J.J.; Janssen, Remie; Jones, M.E.L.; Murakami, Yukihiro; Zeh, Norbert

doi:10.1016/j.jcss.2023.103477

A near-linear kernel for bounded-state parsimony distance

Title

A near-linear kernel for bounded-state parsimony distance

Author

Deen, Elise (Student TU Delft)
van Iersel, L.J.J. (TU Delft Discrete Mathematics and Optimization)
Janssen, Remie (Rijksinstituut voor Volksgezondheid en Milieu (RIVM))
Jones, M.E.L. (TU Delft Discrete Mathematics and Optimization)
Murakami, Yukihiro (TU Delft Discrete Mathematics and Optimization)
Zeh, Norbert (Dalhousie University)

Date

2024

Abstract

The maximum parsimony distance d_MP(T₁,T₂) and the bounded-state maximum parsimony distance d_MP^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_MP^t(T₁,T₂)). While computing d_MP(T₁,T₂) was previously shown to be fixed-parameter tractable with a linear kernel, no such result was known for d_MP^t(T₁,T₂). In this paper, we prove that computing d_MP^t(T₁,T₂) is fixed-parameter tractable for all t. Specifically, we prove that this problem has a kernel of size O(klg⁡k), where k=d_MP^t(T₁,T₂). As the primary analysis tool, we introduce the concept of leg-disjoint incompatible quartets, which may be of independent interest.