2026-07-22T10:24:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17972 2024-03-06T11:00:45Z ddc:004 open_access

On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem Komusiewicz, Christian Linz, Simone Morawietz, Nils Schestag, Jannik phylogenetic trees parameterized complexity tree distances NNI TBR Maximum Parsimony is the problem of computing a most parsimonious phylogenetic tree for a taxa set X from character data for X. A common strategy to attack this notoriously hard problem is to perform a local search over the phylogenetic tree space. Here, one is given a phylogenetic tree T and wants to find a more parsimonious tree in the neighborhood of T. We study the complexity of this problem when the neighborhood contains all trees within distance k for several classic distance functions. For the nearest neighbor interchange (NNI), subtree prune and regraft (SPR), tree bisection and reconnection (TBR), and edge contraction and refinement (ECR) distances, we show that, under the exponential time hypothesis, there are no algorithms with running time |I|^o(k) where |I| is the total input size. Hence, brute-force algorithms with running time |X|^𝒪(k) ⋅ |I| are essentially optimal. In contrast to the above distances, we observe that for the sECR-distance, where the contracted edges are constrained to form a subtree, a better solution within distance k can be found in k^𝒪(k) ⋅ |I|^𝒪(1) time. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Simone Linz and Nils Morawietz and Jannik Schestag 2023 Is Part Of LIPIcs, Volume 259, 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2023.18 urn:nbn:de:0030-drops-179729 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2023.18 eng https://creativecommons.org/licenses/by/4.0/legalcode