A near-linear kernel for bounded-state parsimony distance

Journal article (2024)

Authors

Elise Deen Student
L.J.J. van Iersel Discrete Mathematics and Optimization - EEMCS
Remie Janssen Rijksinstituut voor Volksgezondheid en Milieu (RIVM)
M.E.L. Jones Discrete Mathematics and Optimization - EEMCS
Yukihiro Murakami Discrete Mathematics and Optimization - EEMCS
Norbert Zeh Dalhousie University
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2024 Elise Deen, L.J.J. van Iersel, Remie Janssen, M.E.L. Jones, Yukihiro Murakami, Norbert Zeh
DOI: https://doi.org/10.1016/j.jcss.2023.103477
Parsimony Phylogenetics Maximum parsimony distance Phylogenetic tree Kernelization Distance measure Parameterized complexity
More Info
expand_more

Published Date

2024

Language

English

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

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