Library
local_library Home Repository

A near-linear kernel for bounded-state parsimony distance

Journal Article (2024)
Author(s)

Elise Deen (Student TU Delft)

L.J.J. Van Iersel (TU Delft - Discrete Mathematics and Optimization)

Remie Janssen (Rijksinstituut voor Volksgezondheid en Milieu (RIVM))

M.E.L. Jones (TU Delft - Discrete Mathematics and Optimization)

Yukihiro Murakami (TU Delft - Discrete Mathematics and Optimization)

Norbert Zeh (Dalhousie University)

Research Group
Discrete Mathematics and Optimization
Copyright
© 2024 Elise Deen, L.J.J. van Iersel, Remie Janssen, M.E.L. Jones, Yukihiro Murakami, Norbert Zeh
DOI related publication
https://doi.org/10.1016/j.jcss.2023.103477
More Info
expand_more
Publication Year
2024
Language
English
Copyright
© 2024 Elise Deen, L.J.J. van Iersel, Remie Janssen, M.E.L. Jones, Yukihiro Murakami, Norbert Zeh
Research Group
Discrete Mathematics and Optimization
Volume number
140
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

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.