Recognizing Level-k-Based Phylogenetic Networks is NP-Complete

Abstract 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 \ge 1$$ k ≥ 1 , it is NP-complete to decide whether the minimum level is at most k .

Authors

Institutions

Publication Details

Journal
Bulletin of Mathematical Biology
Published
2026-11-15
DOI
https://doi.org/10.1007/s11538-026-01789-y
Citations
1
Primary Topic
Genomics and Phylogenetic Studies
Type
article
Field-Weighted Citation Impact
1.16
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Recognizing Level-k-Based Phylogenetic Networks is NP-Complete

Takatora Suzuki
1 citations
Bulletin of Mathematical Biology
Genomics and Phylogenetic Studies
1.16
article

Recognizing Level-k-Based Phylogenetic Networks is NP-Complete

Takatora Suzuki
article en
1 citations

Abstract

Abstract 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 \ge 1$$ k ≥ 1 , it is NP-complete to decide whether the minimum level is at most k .

Bulletin of Mathematical BiologyVol. 88(12)
Waseda University (JP)
Openalex Percentile: Top 31%
Genomics and Phylogenetic Studies
1.16
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon