License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2023.18
URN: urn:nbn:de:0030-drops-179729
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17972/
Komusiewicz, Christian ;
Linz, Simone ;
Morawietz, Nils ;
Schestag, Jannik
On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem
Abstract
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.
BibTeX - Entry
@InProceedings{komusiewicz_et_al:LIPIcs.CPM.2023.18,
author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik},
title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}},
booktitle = {34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
pages = {18:1--18:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-276-1},
ISSN = {1868-8969},
year = {2023},
volume = {259},
editor = {Bulteau, Laurent and Lipt\'{a}k, Zsuzsanna},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17972},
URN = {urn:nbn:de:0030-drops-179729},
doi = {10.4230/LIPIcs.CPM.2023.18},
annote = {Keywords: phylogenetic trees, parameterized complexity, tree distances, NNI, TBR}
}
|
Keywords: |
|
phylogenetic trees, parameterized complexity, tree distances, NNI, TBR |
|
Collection: |
|
34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
21.06.2023 |
