A near-linear kernel for bounded-state parsimony distance

Elise Deen, Leo van Iersel, Remie Janssen, Mark Jones*, Yukihiro Murakami, Norbert Zeh

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

9 Downloads (Pure)

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.

Original languageEnglish
Article number103477
Number of pages21
JournalJournal of Computer and System Sciences
Volume140
DOIs
Publication statusPublished - 2024

Keywords

  • Distance measure
  • Kernelization
  • Maximum parsimony distance
  • Parameterized complexity
  • Parsimony
  • Phylogenetic tree
  • Phylogenetics

Fingerprint

Dive into the research topics of 'A near-linear kernel for bounded-state parsimony distance'. Together they form a unique fingerprint.

Cite this