Exploiting Low Scanwidth to Resolve Soft Polytomies
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Exploiting Low Scanwidth to Resolve Soft Polytomies".
Paper summary: Tom: We just touched on the core idea of "Exploiting Low Scanwidth to Resolve Soft Polytomies," which is about using the structure of the network to make that containment problem tractable when dealing with uncertainty.
Jane: Exactly, the paper states that for many practical phylogenetic networks, their scanwidth is low, and by exploiting that fact through a bottom-up dynamic programming approach along a tree extension, they can solve SOFT TREE CONTAINMENT efficiently.
Lu: The thesis of the paper is showing how to go from a general network problem to one solvable in time proportional to two to the scanwidth plus one times log of four times the scanwidth plus four times n cubed, where k is defined as the scanwidth plus n.
Meng: So, if we have a network that isn't super complex structurally, like those with low scanwidth, this algorithm gives us a concrete way to check compatibility with a tree without waiting for an intractable solution.
Lalam: They also showed that the problem boils down to finding a valid signature of the form GWS v based on HWS v, which is essentially how they verify if the network softly displays the target tree.
Tom: That means they've mapped out a way to systematically check for those soft polytomies using this scanwidth metric instead of brute force or something exponentially worse.
Jane: It matters because the classical statement of TREE CONTAINMENT isn't robust to poorly supported branches, and SOFT TREE CONTAINMENT allows us to handle that uncertainty by allowing branch contractions if they are weakly supported.
Lu: They also note that this is a generalization of the CLUSTER CONTAINMENT problem, which already had polynomial solutions for binary networks of constant level.
Meng: So, what’s the real-world impact here? It means we can finally use these network models more reliably in scenarios where our data isn't perfectly resolved and we have to make some assumptions about those branches.
Lalam: The implication is that if you're working with networks where the scanwidth is low, this algorithm gives you a polynomial time solution for a problem that was previously considered hard.
Tom: And they also provide a reduction to turn any network into a binary one in polynomial time while preserving the trees it softly displays, which makes the technique more broadly applicable.
Conclusion: Jane: So we’ve covered how this paper, "Exploiting Low Scanwidth to Resolve Soft Polytomies," tackles the TREE CONTAINMENT problem by focusing on low scanwidth networks and using a dynamic programming approach with soft polytomies.
Tom: The authors are showing that when you restrict your focus to networks with low scanwidth, you can solve this containment problem in time proportional to two to the scanwidth plus one times log of four times the scanwidth plus four times n cubed.
Lu: This is important because it gives a concrete computational tool for handling uncertainty in phylogenetic network data, moving beyond the limitations of classical TREE CONTAINMENT which struggles with poorly supported branches.
Meng: From an engineering standpoint, this suggests that if our real-world biological models naturally have low scanwidth, we can deploy algorithms to check compatibility with trees much faster than before.
Lalam: The paper concludes that a network softly displays a target tree if and only if there exists a valid signature of the form GWS v based on HWS v, which is the definitive test they developed for this soft containment condition.
Jane: So, in simple terms, they’ve found an efficient way to check if a phylogenetic network is compatible with a tree even when some branches are fuzzy or uncertain.
Tom: It's about leveraging the structural property of low scanwidth networks to make a hard problem easier to solve, which opens up new possibilities for modeling complex evolutionary histories.
Sebastian Bruchhold, Mathias Weller
Technische Universitat Berlin · LIGM, CNRS, Univ Gustave Eiffel
cs.DS
Submitted: 2025-11-25
Updated: 2026-08-24
Comments: 24 pages. Accepted at DMTCS. An extended abstract appeared in the proceedings of SOFSEM 2026
Journal ref: SOFSEM 2026: Theory and Practice of Computer Science, volume 16448 of Lecture Notes in Computer Science, pages 332-346, 2026
DOI: 10.1007/978-3-032-17801-5_25
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer…
Key concepts
- TREE CONTAINMENT problem
- This is the core computational task: determining if a given phylogenetic network structure can be represented by a specific phylogenetic tree. The classical version is too strict for real biological data, so this problem addresses that limitation.
- SOFT TREE CONTAINMENT
- A relaxed version of tree containment that accounts for uncertainty in biological data, specifically 'soft polytomies.' This framework allows the algorithm to handle poorly supported branches by permitting the 'undoing' of branch contractions.
- Scanwidth
- A measure similar to treewidth but adapted for phylogenetic networks, respecting arc direction. Low scanwidth is crucial because it makes the problem tractable, enabling a bottom-up dynamic programming approach instead of exponential complexity.
Terminology
Summary
Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer, and this paper presents an algorithm that solves SOFT TREE CONTAINMENT in time 2O(∆T ·k·log(k))·nO(1) where k:= sw(Γ) +∆N
Problem Formulation and Motivation
The fundamental computational problem addressed is the TREE CONTAINMENT problem, which asks whether a given phylogenetic network is compatible with a given phylogenetic tree The classical statement of the problem is not robust to poorly supported branches in biological data, possibly leading to false negatives To address this limitation, a relaxed version called SOFT TREE CONTAINMENT was introduced by Bentert, Mal´ık, and Weller [SWAT’18] which accounts for uncertainty in the form of so-called “soft polytomies” This framework permits undoing
contractions of poorly supported branches
Scanwidth and Tractability
The algorithm leverages the fact that phylogenetic networks encountered in practice often exhibit low scanwidth, making the problem more tractable Scanwidth is a measure similar to treewidth but respecting the direction of arcs, allowing for a bottom-up dynamic-programming approach The scanwidth of a DAG D is defined as the minimum swD(Γ) over all tree extensions Γ of D
Algorithm Structure and Dynamic Programming
The algorithm first makes the network binary through “stretching” and “in-splitting” This special case is then solved via bottom-up dynamic programming along the given tree extension The core of the decision process involves generating valid signatures [B, S, ψ] and computing signatures in a bottom-up traversal of Γ The procedure POPULATEGWS constructs the set GWS v based on HWS v
Complexity and Reduction
The running time of the algorithm is bounded by O∗(2∆T ·(sw(Γ)+1)·log2(4·sw(Γ)+4)) time This bound is derived from Lemma 2, which shows that for each set B ⊆ A(N), there are at most (4 ·B)∆T ·B valid signatures of the form [B, S, ψ] Furthermore, a reduction maps any network to a binary one in polynomial time while preserving the trees that the network softly displays
Conclusion and Future Directions
The paper concludes by showing that N∗ softly displays T if and only if there exists a valid signature of the form [GWv(Γ), a, ψ] The dependence on scanwidth is essential for tractability, motivating future work to obtain low-scanwidth tree extensions in reasonable time The techniques developed are also relevant for tackling other containment problems such as NETWORK CONTAINMENT
--- Page 6 ---
Pruning redundant reasoning tokens
Phylogenetic networks allow modeling reticulate evolution, capturing events such as hybridization and horizontal gene transfer, and this paper presents an algorithm that solves SOFT TREE CONTAINMENT in time 2O(∆T ·k·log(k))·nO(1) where k:= sw(Γ) +∆N
How the training signal is built
The algorithm first makes the network binary through “stretching” and “in-splitting” This special case is then solved via bottom-up dynamic programming along the given tree extension The core of the decision process involves generating valid signatures [B, S, ψ] and computing signatures in a bottom-up traversal of Γ The procedure POPULATEGWS constructs the set GWS v based on HWS v
Where the gains come from
The running time of the algorithm is bounded by O∗(2∆T ·(sw(Γ)+1)·log2(4·sw(Γ)+4)) time This bound is derived from Lemma 2, which shows that for each set B ⊆ A(N), there are at most (4 ·B)∆T ·B valid signatures of the form [B, S, ψ] Furthermore, a reduction maps any network to a binary one in polynomial time while preserving the trees that the network softly displays
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Implementation of a parameterized algorithm for SOFT TREE CONTAINMENT that solves it in O(2DeltaT ·k·log(k)) time by leveraging low scanwidth, where k is defined as sw(Gamma) + DeltaN. This allows the system to efficiently decide if a phylogenetic network softly displays a phylogenetic tree, even for large instances encountered in practice.
-
Ability to handle high-degree vertices in networks by resolving them into binary trees using exhaustive out-splitting and in-splitting, which is formalized by Definitions 1 and 2, enabling the system to account for uncertainty represented as
soft polytomies.
-
Computation of soft display relations via a dynamic programming approach along a canonical tree extension Gamma, utilizing signatures [B, S, psi] to decide containment by checking validity conditions such as Lemma 5. This allows the system to generate valid signatures and determine the final answer based on Lemma 6.
-
Reduction of arbitrary phylogenetic networks to equivalent binary networks via stretching and in-splitting gadgets defined in Definition 12 and related procedures, ensuring that the soft display property is preserved across this transformation (Lemma 8).
-
Efficient computation of scanwidth bounds under network modifications, specifically showing that sw(str(N)) <= sw(N) + 2 · DeltaN through Lemma 10, which allows the system to bound its running time based on the initial scanwidth and maximum out-degree.
Abstract
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 times k times (k)) times n O(1) time, where k = sw(Γ) + Δ N, with Δ T and Δ N denoting the maximum out-degrees in the tree and the network, respectively, and 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.
Sources
- Solving Tree Containment Problem for Reticulation-visible Networks with Optimal Running Time
- Tree Containment Parameterized by Scanwidth
Related papers
- PHastR: Faster Minimal Perfect Hashing with Rotated Layouts
- Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with k-SUM in 2D
- Polynomial-time computation of p-contraction fixed points for even p
- Separations Between Submodular-Like Graph Widths
- Bounded Integer Programming in Almost N 2d Time
- Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles