pith. sign in

arxiv: 2605.31071 · v2 · pith:DQEQ4SBXnew · submitted 2026-05-29 · 💻 cs.DS · cs.CC· q-bio.PE

Tree Containment Parameterized by Scanwidth

Leo van Iersel , Mark Jones , Mathias Weller This is my paper

Pith reviewed 2026-06-28 20:25 UTC · model grok-4.3

classification 💻 cs.DS cs.CCq-bio.PE
keywords Tree ContainmentScanwidthParameterized AlgorithmsPhylogenetic NetworksExponential Time HypothesisDirected Cutwidth
0
0 comments X

The pith

Tree Containment can be decided in O(4^{k + k log k} n + n m^2) time given a tree-extension of width k.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a way to decide whether one rooted phylogenetic tree embeds into another rooted phylogenetic network when the network is supplied with an auxiliary tree-extension of small width k. The resulting algorithm runs in time exponential only in k plus a k log k term, multiplied by the network size. A matching lower bound under the Exponential Time Hypothesis shows that no substantially faster algorithm exists, even when restricted to binary networks.

Core claim

TREE CONTAINMENT can be solved in O(4^{k + k log k} n + n m^2) time when the input network is supplied with a tree-extension of width k, and no algorithm running in 2^{o(c log c)} n^{O(1)} time exists under the Exponential Time Hypothesis even on binary inputs, where c is the directed cutwidth.

What carries the argument

A tree-extension of width k, a rooted tree that extends the network such that at most k arcs cross any cut, used to drive dynamic programming that tracks possible embeddings of the input tree.

If this is right

  • Networks whose scanwidth is bounded by a small constant admit polynomial-time solutions for Tree Containment.
  • The exponential dependence on k cannot be improved to 2^{o(k log k)} under ETH.
  • The same lower bound applies when the input network is required to be binary.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same tree-extension technique may yield FPT algorithms for other containment-style problems on phylogenetic networks.
  • Heuristics that compute or approximate small-width tree-extensions would make the algorithm practical on real data.
  • The log k factor in the exponent suggests that scanwidth-based methods will require careful implementation to avoid hidden polynomial overhead.

Load-bearing premise

The network is given together with a tree-extension whose width k is small.

What would settle it

An algorithm that solves Tree Containment on binary networks in 2^{o(c log c)} n^{O(1)} time for directed cutwidth c, or an instance where the stated runtime bound is exceeded.

Figures

Figures reproduced from arXiv: 2605.31071 by Leo van Iersel, Mark Jones, Mathias Weller.

Figure 1
Figure 1. Figure 1: Illustration of signatures (v, S,ψ, deg+ Γ (v)) and (v, S ′ , ψ′ , deg+ Γ (v)), where ψ and ψ′ map each of the colored arcs marked as S (top right) and S ′ (bottom right), respectively, to the arc of the same color in GWv (Γ ) (left, middle). Note that S ′ does not contain blue arcs, so ψ′ does not map blue arcs. Left: input network N with arcs of GWv (Γ ) in bold and color. Middle: tree extension Γ (thick… view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of the three main cases occurring in the algorithm. [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Example of Construction 1. Top left: gadget Qℓ . Bottom left: gadget Rℓ . Right: the Qi and the Ri are strung together such as to form a chain whose cutwidth is bounded in k. Construction 1 (see [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Illustration of the tree T constructed in Construction 2. Source-nodes in G are indicated in gray. From Disjoint Paths to Tree Containment. Construction 1 can be modified to show that TREE CONTAINMENT cannot be solved in 2 o(k log k)n O(1) time, where k is the scanwidth of the input network. To this end, we turn the input DAG into a (binary) phylogenetic network N and we turn the demand-set for disjoint pa… view at source ↗
read the original abstract

TREE CONTAINMENT is a central decision problem in mathematical phylogenetics, asking whether a given rooted phylogenetic tree is embeddable in ("displayed by") a given rooted phylogenetic network. While the problem is NP-complete for general networks, many algorithmic advances have relied on structural parameters that capture how "tree-like" a network is. In this paper we investigate TREE CONTAINMENT under the structural parameter scanwidth, a directed width measure generalizing popular parameters measuring tree-likeness of phylogenetic networks. We first present a parameterized algorithm that solves the problem in $O(4^{k + k\log{k}} n + nm^2)$ time, where $n$ and $m$ are the numbers of nodes and arcs in the network and $k$ is the width of a given tree-extension. Complementing this upper bound, we prove a matching lower bound under the Exponential-Time Hypothesis (ETH), showing that there is no algorithm for TREE CONTAINMENT that runs in $2^{o(c\log{c})} n^{O(1)}$ time, even on binary inputs, where $c$ is the directed cutwidth of the input network, which upper-bounds the scanwidth $k$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript claims an FPT algorithm for TREE CONTAINMENT parameterized by the width k of a given tree-extension, with runtime O(4^{k + k log k} n + n m^2), and a matching ETH lower bound of 2^{o(c log c)} n^{O(1)} even on binary networks, where c is the directed cutwidth.

Significance. This provides a tight characterization of the parameterized complexity of TREE CONTAINMENT under scanwidth, a useful structural parameter for phylogenetic networks. The matching bounds and the fact that the lower bound holds even for binary inputs are notable strengths.

minor comments (1)
  1. [Abstract] The runtime bound uses 'log' without specifying the base; this should be clarified as it affects the constant factors in the exponent.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of our manuscript and for recommending acceptance. We are pleased that the tight FPT algorithm and matching ETH lower bound, including the binary case, were recognized as notable contributions to the parameterized complexity of TREE CONTAINMENT under scanwidth.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper supplies an explicit dynamic-programming algorithm whose runtime is derived directly from the given tree-extension width k (standard FPT setup) and proves a lower bound by reduction from an external assumption (ETH) that does not depend on any fitted quantity or self-referential definition inside the paper. The directed-cutwidth parameter c is related to scanwidth only by the stated inequality c ≥ k; the matching exponent form is a deliberate design choice, not a circular reduction. No self-citation is load-bearing for the central claims, and no ansatz or renaming is used to derive the stated bounds.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claims rest on the standard Exponential Time Hypothesis from complexity theory and on the graph-theoretic definitions of scanwidth and tree-extensions; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Exponential Time Hypothesis (ETH)
    Invoked to prove the conditional lower bound on running time.

pith-pipeline@v0.9.1-grok · 5745 in / 1225 out tokens · 43331 ms · 2026-06-28T20:25:02.714370+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

25 extracted references · 19 canonical work pages

  1. [1]

    Tree containment with soft polytomies

    Matthias Bentert and Mathias Weller. “Tree containment with soft polytomies”. In:Journal of Graph Algorithms and Applications25.1 (2021), pp. 417–436.DOI:10.7155/jgaa.00565

    work page doi:10.7155/jgaa.00565 2021

  2. [2]

    Scanning Phylogenetic Networks Is NP-hard

    Vincent Berry, Celine Scornavacca, and Mathias Weller. “Scanning Phylogenetic Networks Is NP-hard”. In: Updated version at https : / / hal . science / hal - 02353161. Jan. 2020, pp. 519–530.DOI: 10.1007/978-3-030-38919-2_42

    work page doi:10.1007/978-3-030-38919-2_42 2020

  3. [3]

    A partial k-arboretum of graphs with bounded treewidth

    Hans L. Bodlaender. “A partial k-arboretum of graphs with bounded treewidth”. In:Theoretical Computer Science209.1 (1998), pp. 1–45.ISSN: 0304-3975.DOI:10.1016/S0304-3975(97)00228-4

    work page doi:10.1016/s0304-3975(97)00228-4 1998

  4. [4]

    Exploiting Low Scanwidth to Resolve Soft Polytomies

    Sebastian Bruchhold and Mathias Weller. “Exploiting Low Scanwidth to Resolve Soft Polytomies”. In: Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2026. Lecture Notes in Computer Science. Springer, 2026, pp. 332–346.DOI: 10. 1007/978-3-032-17801-5\_25

    2026

  5. [5]

    Parameterized Algorithms in Bioinformatics: An Overview

    Laurent Bulteau and Mathias Weller. “Parameterized Algorithms in Bioinformatics: An Overview”. In: Algorithms12.12 (2019), p. 256.DOI:10.3390/A12120256. 17

    work page doi:10.3390/a12120256 2019

  6. [6]

    Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

    Rajesh Chitnis, MohammadTaghi Hajiaghayi, and Dániel Marx. “Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset”. In:SIAM Journal on Computing42.4 (2013), pp. 1674–1696.DOI:10.1137/12086217X

    work page doi:10.1137/12086217x 2013

  7. [7]

    Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh

    Marek Cygan, Fedor V . Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Springer International Publishing, 2015.ISBN: 978-3-319-21275-3.DOI: 10.1007/978-3-319-21275-3_14

    work page doi:10.1007/978-3-319-21275-3_14 2015

  8. [8]

    Displaying trees across two phylogenetic networks

    Janosch Döcker, Simone Linz, and Charles Semple. “Displaying trees across two phylogenetic networks”. In:Theoretical Computer Science796 (2019), pp. 129–146.ISSN: 0304-3975.DOI: 10.1016/j.tcs. 2019.09.003

    work page doi:10.1016/j.tcs 2019

  9. [10]

    Solving the tree containment problem in linear time for nearly stable phylogenetic networks

    Philippe Gambette, Andreas D.M. Gunawan, Anthony Labarre, Stéphane Vialette, and Louxin Zhang. “Solving the tree containment problem in linear time for nearly stable phylogenetic networks”. In:Discrete Applied Mathematics246 (2018). The Combinatorics of Graphs and Strings, pp. 62–79.ISSN: 0166-218X. DOI:10.1016/j.dam.2017.07.015

    work page doi:10.1016/j.dam.2017.07.015 2018

  10. [11]

    Do branch lengths help to locate a tree in a phylogenetic network?

    Philippe Gambette, Leo Van Iersel, Steven Kelk, Fabio Pardi, and Celine Scornavacca. “Do branch lengths help to locate a tree in a phylogenetic network?” In:Bulletin of mathematical biology78.9 (2016), pp. 1773–1795.DOI:10.1007/s11538-016-0199-4

    work page doi:10.1007/s11538-016-0199-4 2016

  11. [12]

    Solving the Tree Containment Problem for Reticulation-Visible Networks in Linear Time

    Andreas D. M. Gunawan. “Solving the Tree Containment Problem for Reticulation-Visible Networks in Linear Time”. In:Algorithms for Computational Biology. Cham: Springer International Publishing, 2018, pp. 24–36.ISBN: 978-3-319-91938-6.DOI:10.1007/978-3-319-91938-6_3

    work page doi:10.1007/978-3-319-91938-6_3 2018

  12. [13]

    Computing the scanwidth of directed acyclic graphs

    Niels Holtgrefe. “Computing the scanwidth of directed acyclic graphs”. available athttp://resolver. tudelft.nl/uuid:9c82fd2a-5841-4aac-8e40-d4d22542cdf5 . MA thesis. Delft University of Technology , Delft, The Netherlands, July 2023

    2023

  13. [14]

    Huson, Regula Rupp, and Celine Scornavacca.Phylogenetic Networks: Concepts, Algorithms and Applications

    Daniel H. Huson, Regula Rupp, and Celine Scornavacca.Phylogenetic Networks: Concepts, Algorithms and Applications. Cambridge University Press, 2010

    2010

  14. [15]

    Complexity of k-SAT

    R. Impagliazzo and R. Paturi. “Complexity of k-SAT”. In:Proceedings of the 14th Annual IEEE Conference on Computational Complexity. 1999, pp. 237–240.DOI:10.1109/CCC.1999.766282

    work page doi:10.1109/ccc.1999.766282 1999

  15. [16]

    Which Problems Have Strongly Exponential Complexity?

    Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. “Which Problems Have Strongly Exponential Complexity?” In:Journal of Computer and System Sciences63.4 (2001), pp. 512–530.ISSN: 0022-0000. DOI:10.1006/jcss.2001.1774

    work page doi:10.1006/jcss.2001.1774 2001

  16. [17]

    Seeing the trees and their branches in the network is hard

    Iyad A Kanj, Luay Nakhleh, Cuong Than, and Ge Xia. “Seeing the trees and their branches in the network is hard”. In:Theoretical Computer Science401.1-3 (2008), pp. 153–164.DOI: 10.1016/j.tcs.2008. 04.019

    work page doi:10.1016/j.tcs.2008 2008

  17. [18]

    An Improved Parameterized Algorithm for Treewidth

    Tuukka Korhonen and Daniel Lokshtanov. “An Improved Parameterized Algorithm for Treewidth”. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 528–541.ISBN: 9781450399135.DOI: 10.1145/ 3564246.3585245

    work page arXiv 2023

  18. [19]

    Counting Trees in a Phylogenetic Network Is #P-Complete

    Simone Linz, Katherine St. John, and Charles Semple. “Counting Trees in a Phylogenetic Network Is #P-Complete”. In:SIAM Journal on Computing42.4 (2013), pp. 1768–1776.DOI: 10.1137/12089394X

    work page doi:10.1137/12089394x 2013

  19. [20]

    Slightly Superexponential Parameterized Prob- lems

    Daniel Lokshtanov, Dániel Marx, and Saket Saurabh. “Slightly Superexponential Parameterized Prob- lems”. In:SIAM J. Comput.47.3 (2018), pp. 675–702.DOI:10.1137/16M1104834

    work page doi:10.1137/16m1104834 2018

  20. [21]

    Parameterized graph separation problems

    Dániel Marx. “Parameterized graph separation problems”. In:Theoretical Computer Science351.3 (2006). Parameterized and Exact Computation, pp. 394–406.ISSN: 0304-3975.DOI: https://doi.org/10. 1016/j.tcs.2005.10.007

    2006

  21. [22]

    Jannik Schestag and Norbert Zeh.The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth. 2026. arXiv:2602.06903 [cs.CC].URL:https://arxiv.org/abs/2602.06903

    work page arXiv 2026

  22. [23]

    Locating a tree in a phylogenetic network

    Leo van Iersel, Charles Semple, and Mike Steel. “Locating a tree in a phylogenetic network”. In:Informa- tion Processing Letters110.23 (2010), pp. 1037–1043.ISSN: 0020-0190.DOI: 10.1016/j.ipl.2010. 07.027. 18

    work page doi:10.1016/j.ipl.2010 2010

  23. [24]

    Embedding phylogenetic trees in networks of low treewidth

    Leo van Iersel, Mark Jones, and Mathias Weller. “Embedding phylogenetic trees in networks of low treewidth”. In:Discrete Mathematics & Theoretical Computer Sciencevol. 25:2, 4 (2023):Discrete Algo- rithms.ISSN: 1365-8050.DOI:10.46298/dmtcs.10116

    work page doi:10.46298/dmtcs.10116 2023

  24. [25]

    Linear-Time Tree Containment in Phylogenetic Networks

    Mathias Weller. “Linear-Time Tree Containment in Phylogenetic Networks”. In:Comparative Genomics. Cham: Springer International Publishing, 2018, pp. 309–323.ISBN: 978-3-030-00834-5.DOI: 10.1007/ 978-3-030-00834-5_18

    2018

  25. [26]

    Seminar in Discrete Mathematics and Optimization, Delft University of Technology

    Norbert Zeh.An FPT Algorithm for Scanwidth. Seminar in Discrete Mathematics and Optimization, Delft University of Technology. Talk given at TU Delft. Sept. 2023.URL: https://www.tudelft.nl/ en/events/2023/eemcs/diam/seminars-in-discrete-mathematics-and-optimization/ dmo-norbert-zeh-an-fpt-algorithm-for-scanwidth. 19

    2023