Sebastian Bruchhold

 

Fakultät II - Mathematik und Naturwissenschaften
Institut für Mathematik, MA 5-2
Technische Universität Berlin
Straße des 17. Juni 136
10623 Berlin

Office: MA 664
Email: (lastname)@math.tu-berlin.de

0009-0003-7413-4263

Publications

to appear

• Exploiting Low Scanwidth to Resolve Soft Polytomies (Sebastian Bruchhold and Mathias Weller)
  SOFSEM 2026 – Proc. 51st International Conference on Current Trends in Theory and Practice of Computer Science.
  PDF arxiv Bibtex Abstract
  @inproceedings{BruchholdWeller2026,
  author = {Sebastian Bruchhold and Mathias Weller},
  title = {Exploiting Low Scanwidth to Resolve Soft Polytomies},
  booktitle = {SOFSEM 2026 – Proc. 51st International Conference on Current Trends in Theory and Practice of Computer Science},
  year = {to appear},
  arxiv = {2511.20771},
  }
  
  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(\Delta_T \cdot k \cdot \log(k))} \cdot n^{O(1)}$ time, where $k = \operatorname{sw}(\Gamma) + \Delta_N$, with $\Delta_T$ and $\Delta_N$ denoting the maximum out-degrees in the tree and the network, respectively, and $\operatorname{sw}(\Gamma)$ 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.

Theses

• On (Node-)Scanwidth and Its Algorithmic Applications (Sebastian Bruchhold)
  Master's thesis, 2024.
  pdf doi
• A Simple and Robust Measure of Triadic Closure: Algorithmic and Structural Aspects (Sebastian Bruchhold)
  Bachelor's thesis, 2022.
  pdf doi