EUVIMEDEUVIMED entdecken
Crossref

Exploiting Low Scanwidth to Resolve Soft Polytomies

Sebastian Bruchhold, Mathias Weller

Discrete Mathematics & Theoretical Computer Science · 16.11.2026 · vol. 28:4, SOFSEM 2026 (Special issues)

DOI: 10.46298/dmtcs.17720 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Discrete Mathematics & Theoretical Computer Science, online erschienen am 16.11.2026. Verfasst von Sebastian Bruchhold und 1 weiteren Autor:innen.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer. A fundamental computational problem in this context is the Tree Containment problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree. However, the classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives. In an effort to address this, a relaxed version that accounts for uncertainty, called Soft Tree Containment, has been introduced by Bentert, Malík, and Weller [SWAT'18]. We present an algorithm that solves Soft Tree Containment in $2^{O(Δ_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k = \operatorname{sw}(Γ) + Δ_N$, with $Δ_T$ and $Δ_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\operatorname{sw}(Γ)$ denoting the "scanwidth" [Berry, Scornavacca, and Weller, SOFSEM'20] of a given tree extension of the network, while $n$ is the input size. Our approach leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable.

Zitieren

APA

Bruchhold, S., & Weller, M. (2026). Exploiting Low Scanwidth to Resolve Soft Polytomies. Discrete Mathematics & Theoretical Computer Science, vol. 28:4, SOFSEM 2026(Special issues). https://doi.org/10.46298/dmtcs.17720

Vancouver

Bruchhold S, Weller M. Exploiting Low Scanwidth to Resolve Soft Polytomies. Discrete Mathematics & Theoretical Computer Science. 2026;vol. 28:4, SOFSEM 2026(Special issues). doi:10.46298/dmtcs.17720

BibTeX
@article{Bruchhold2026,
  author = {Bruchhold, Sebastian and Weller, Mathias},
  title = {Exploiting Low Scanwidth to Resolve Soft Polytomies},
  journal = {Discrete Mathematics & Theoretical Computer Science},
  year = {2026},
  volume = {vol. 28:4, SOFSEM 2026},
  number = {Special issues},
  doi = {10.46298/dmtcs.17720}
}
Kostenlos starten →