Recognizing Level-k-Based Phylogenetic Networks is NP-Complete
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916049471930368 |
|---|---|
| author | Suzuki, Takatora |
| author_facet | Suzuki, Takatora |
| contents | Phylogenetic networks generalize phylogenetic trees by representing reticulate evolution. Tree-based networks and their support trees have been extensively studied, but not all networks are tree-based. To measure how far such networks are from being tree-based, Suzuki and Hayamizu (2025) formulated the problem of finding the support network with minimum level of a given rooted almost-binary phylogenetic network. They conjectured that this problem is NP-hard and provided exponential-time algorithms. In this paper, we prove this conjecture by showing that, for every fixed integer $k \geq 1$, it is NP-complete to decide whether the minimum level is at most $k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_26852 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Recognizing Level-k-Based Phylogenetic Networks is NP-Complete Suzuki, Takatora Populations and Evolution Discrete Mathematics 05C20 (Primary), 05C85, 68Q17, 92D15 (Secondary) Phylogenetic networks generalize phylogenetic trees by representing reticulate evolution. Tree-based networks and their support trees have been extensively studied, but not all networks are tree-based. To measure how far such networks are from being tree-based, Suzuki and Hayamizu (2025) formulated the problem of finding the support network with minimum level of a given rooted almost-binary phylogenetic network. They conjectured that this problem is NP-hard and provided exponential-time algorithms. In this paper, we prove this conjecture by showing that, for every fixed integer $k \geq 1$, it is NP-complete to decide whether the minimum level is at most $k$. |
| title | Recognizing Level-k-Based Phylogenetic Networks is NP-Complete |
| topic | Populations and Evolution Discrete Mathematics 05C20 (Primary), 05C85, 68Q17, 92D15 (Secondary) |
| url | https://arxiv.org/abs/2605.26852 |