Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks

Alexey Markin; Oliver Eulenstein; Sriram Vijendran

REVIEW 3 major objections 3 minor 25 references

Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Level-k networks have treewidth at most (k+3)/2

desk verdict Genuinely new bounds on treewidth of level-k phylogenetic networks, with a real but repairable gap in the proof of the main upper bound. read the letter →

arxiv 2411.13380 v1 pith:WJNCDZ4F submitted 2024-11-20 q-bio.PE math.CO

Alexey Markin , Sriram Vijendran , Oliver Eulenstein This is my paper · ORCID

classification q-bio.PEmath.CO MSC 05C8505C8368R10

keywords phylogeneticnetworkstreewidthlevel-kreticulationnumbergraphminorstreedecompositionexpandergraphssmallparsimony

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper establishes that the level of a rooted phylogenetic network—the maximum number of edges that must be removed from a biconnected component to turn it into a tree—controls its treewidth in a linear way. It proves an upper bound of (k+3)/2 on the treewidth of any level-k network, and a sharper upper bound of about (1/3+2ε)k for large k under a mild condition. It also proves that for large k, some level-k networks have treewidth at least k/13, so treewidth cannot be sublinear in level. If these bounds hold, hard problems like small parsimony and phylogenetic diversity maximization become polynomial-time solvable on networks of constant level, and explicit tree decompositions can be built for networks produced by bounded-level inference tools.

What carries the argument

The load-bearing tool is Lemma 1, a minor–level correspondence: a biconnected graph with m edges and n nodes can be embedded as a minor of a network of level exactly m-n+1, and any network that has it as a minor must have level at least m-n+1. This lets the authors carry a graph-theoretic argument by tracking how many edges and nodes survive after deleting a vertex, and it is also used constructively to build networks from expander graphs for the lower bound. The proof additionally relies on the standard fact that treewidth equals the maximum treewidth over biconnected components, and on an existing result bounding the treewidth of any subcubic graph in terms of its number of vertices.

What would settle it

A level-3 network whose treewidth is 4 would disprove the upper bound of (k+3)/2. A computational search for such a network—or a proof that none exists—would directly test the contested induction step, since the paper's bound rests on the claim that deleting a degree-3 vertex lowers the effective level by at least 2.

Watch

Extended reading notes

Core claim

The main discovery is a tight linear relationship between two graph parameters: the level of a phylogenetic network and its treewidth. The proof starts from a lemma that converts any biconnected graph with m edges and n nodes into a network of level m-n+1, and conversely requires any network containing such a graph as a minor to have level at least that large. This converts level bounds into node-count bounds on the underlying graph, which in turn bound treewidth. Theorem 1 then gives tw(N) ≤ (k+3)/2 via induction on the level; Theorem 2 improves this to roughly k/3 for large k using a known bound on treewidth of graphs of maximum degree 3; and Theorem 3 shows that 5-regular expander graphs, realized as level-(3n/2−1) networks, have treewidth at least n/4, giving the k/13 lower bound.

Load-bearing premise

The proof of Theorem 1 assumes, without proof, that after deleting a degree-3 vertex from a biconnected component of a level-k network, the remaining graph can be viewed as a level-(k−2) network via Lemma 1, even though that remaining graph need not itself be biconnected.

Editorial extensions

If this is right

Small parsimony and phylogenetic diversity maximization, both NP-hard in general, are polynomial-time solvable on level-k networks when k is fixed, because they are solvable in polynomial time on graphs of bounded treewidth.
Networks returned by tools like SNAQ, which guarantee a bounded level, come with an explicit tree decomposition of width (k+3)/2 by the proof of Theorem 1.
For large k, the treewidth is at most roughly k/3, so treewidth-parameterized algorithms remain efficient even for moderately high-level networks.
The k/13 lower bound shows that the linear dependence on k is unavoidable: there are level-k networks whose treewidth grows linearly with k.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The gap between the k/13 lower bound and the ~k/3 upper bound leaves open the exact constant for the maximum treewidth of level-k networks; if the upper bound is closer to the truth, then practical networks with level in the tens still have treewidth below about 30, making dynamic programs viable.
The explicit construction behind Theorem 1 could be turned into an algorithm that takes a level-k network and directly outputs a tree decomposition of width (k+3)/2, without first solving an NP-hard treewidth computation.
The minor–level lemma may be useful beyond treewidth: it could yield linear bounds on other structural parameters such as pathwidth or branchwidth for level-k networks, or help design kernelization algorithms for network comparisons.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a real contribution. It gives the best known upper bounds on treewidth of level-k phylogenetic networks—(k+3)/2 for all k, and (1/3+δ)k for large k—and the first linear lower bound, k/13. The bounds are new and the techniques are sensible. The lower bound actually gives about k/12 before the floor slack, so the k/13 statement is conservative. The asymptotic upper bound is a clean application of the Fomin–Høie pathwidth bound to cubic graphs, and the reduction to binary networks via node splitting is sound.

The main weakness is in the proof of Theorem 1. The proof removes a degree-3 node from the maximum-treewidth biconnected component M, leaving G', and then applies Lemma 1 to turn G' into a level-(k-2) network M'. But Lemma 1 requires biconnected input, and G' is only connected. Also, the level formula |E(G')|-|V(G')|+1 is the total cyclomatic number; for a non-biconnected graph the level of a constructed network would be the maximum over blocks, which can be smaller. The argument still goes through if you decompose G' into biconnected blocks, observe each has cyclomatic number at most k-2, apply the induction to each block, and then use tw(G') = max over blocks. The proof also omits the explicit step tw(G') ≤ tw(M'), which follows by minor-monotonicity once M' exists. So the gap is real but repairable without changing the result.

One minor presentation issue: Theorem 2 says every maximal biconnected component has reticulation number exactly k. The proof only needs the component with maximum reticulation number, so the theorem is slightly narrower than necessary but not wrong.

This paper is for people working on treewidth-based algorithms for phylogenetic networks and on structural graph theory of network classes. It's a solid candidate for a serious referee. I would send it to review with a request to fix Theorem 1's induction; after that, it should be a strong paper.

Referee Report

3 major / 3 minor

Summary. The paper studies the treewidth of the undirected graph underlying a rooted level-k phylogenetic network. It proves (Theorem 1) an upper bound tw(N) ≤ (k+3)/2 by induction on k; (Theorem 2) for large k, assuming every maximal biconnected component has reticulation number k, an improved upper bound tw(N) < (1/3+2ε)k, using binarization, degree-2 contractions, and a subcubic treewidth bound; and (Theorem 3) a lower bound of roughly k/13 on the maximum treewidth among level-k networks, using 5-regular expander graphs. The paper also restates a lemma of Coronado et al. connecting biconnected minors to level and gives a short self-contained proof of that lemma.

Significance. These are the best-known linear bounds relating level and treewidth for phylogenetic networks, and they improve the previous k+1 upper bound. If correct, the upper bounds imply that treewidth-parameterized algorithms for problems such as small parsimony and some diversity maximization variants run in time exponential in roughly k/2 (or k/3 for large k) on bounded-level networks; the k/13 lower bound shows that linear dependence is unavoidable. The paper is mostly self-contained in its use of Lemma 1, and it clearly identifies the external tools it relies on. The proofs are concise, but as detailed below the main induction and the parametric range of the lower bound need repair or clarification.

major comments (3)

[Section 4, proof of Theorem 1] Lemma 1 applies only to biconnected graphs, but after deleting a degree-3 or higher vertex v from the biconnected component M, the graph G' = GM - v is not necessarily biconnected; for example, if M is a theta graph, deleting one endpoint leaves a graph whose blocks are paths and edges. Consequently, the step 'By Lemma 1, we can turn G' into a directed network M' with level k' = |E(G')|-|V(G')|+1' is not justified as written, and the displayed equality misstates the level of a non-biconnected graph, for which the level is the maximum of |E(B)|-|V(B)|+1 over the biconnected blocks B, not the total cyclomatic number. This is load-bearing because the induction hypothesis needs a level-(k-2) network whose treewidth bounds tw(G') and hence tw(M). The gap is repairable: decompose G' into blocks, note each block has cyclomatic number at most |E(G')|-|V(G')|+1 ≤ k-2, apply the induction hypothesis to each block as a minor of a level-(k-2) network from Lemma 1, and use tw(G') = max_B tw(B). The paragraph should be rewritten with this argument or an equivalent one.
[Section 4, Theorem 2] The theorem is stated only for networks in which every maximal biconnected component has reticulation number k, but the abstract and conclusion advertise the improved (1/3+δ)k bound for all large-k level-k networks. The proof's sentence 'Note that we enforced the reticulation number of M to be k' is not justified: binarizing by splitting may change the block decomposition, and a level-k network may contain components of lower reticulation number. The intended bound can be recovered because for the chosen component M, Lemma 1 gives k ≥ |E(M)|-|V(M)|+1 = n3/2+1 regardless of whether that block's own reticulation number equals k; I recommend relaxing the hypothesis accordingly or explicitly restricting the stated claim to the class covered by the current statement.
[Section 5, Theorem 3] The proof invokes Lemma 3, which as stated guarantees only 'some large n' for the 5-regular expander, and then solves k = (3/2)n+1. This proves the lower bound only for the corresponding values of k (possibly a single value, depending on the reading of Lemma 3), not for every sufficiently large integer k as the theorem statement claims. Please clarify that expander graphs are available for arbitrarily large n, or add an argument (for example, adding chords to the expander while preserving biconnectivity and nondecreasing treewidth and expansion) that extends the bound to all large k.

minor comments (3)

[Section 4, opening sentence] There is a typo: 'levek-k' should be 'level-k'.
[Abstract and Section 4] The abstract's claim that the first bound 'allows us to construct an explicit tree decomposition of width (k+3)/2' is stronger than what is proved; the proof shows existence of such a decomposition via standard treewidth arguments, not an explicit construction. Please reword or provide the construction.
[Section 2, Observation 2] The proof of Observation 2 should state explicitly that it assumes simple graphs or otherwise address parallel edges, since for a multigraph with two vertices and parallel edges the treewidth lower bound used in the proof does not hold.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: the treewidth bounds are derived from independent graph-theoretic results and a re-proved minor lemma, with no fitted parameters and no load-bearing self-citation chain.

full rationale

The paper's central claims are theorem statements about treewidth and level. The derivation does not define level in terms of treewidth or vice versa: level is defined via reticulation numbers of biconnected components, while treewidth is defined via tree decompositions. The main upper bound (Theorem 1) is proved by induction using Lemma 1 (a minor lemma re-proved in Section 3), Bodlaender's biconnected-component treewidth decomposition, the fact that deleting a vertex lowers treewidth by at most one, and the Janssen et al. level-1 bound for the base case. The large-k upper bound (Theorem 2) combines Lemma 1 with Fomin and Høie's sublinear treewidth bound for bounded-degree graphs and a degree-2 contraction argument. The lower bound (Theorem 3) uses a Lubotzky expander and the Grohe-Marx expansion-to-treewidth theorem. Lemma 1 itself is re-derived in Section 3 from the reticulation-number identity and an explicit subdivision construction, not assumed as a black box. None of the cited results is by the present authors, and none assumes the bounds being proven. A reviewer-flagged gap in Theorem 1—invoking Lemma 1 on a graph left after deleting a degree-3 vertex, which need not be biconnected—is a potential correctness or completeness issue in the proof, but it is not circularity: it does not reduce the claimed bound to an input or to a self-citation. Since no fitted value is called a prediction and no load-bearing premise is justified solely by a self-citation, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 7 assumptions · 0 invented entities

The central claims rest on standard graph-theory results cited from the literature, plus a re-proved lemma from Coronado et al. There are no free parameters fitted to data and no new postulated entities.

assumptions (7)

standard math Treewidth of a graph equals the maximum treewidth of its biconnected components (Bodlaender [3]).
Used in Theorem 1 and Theorem 2 to reduce to a single biconnected component.
standard math Edge contraction cannot increase treewidth (Robertson-Seymour [20]).
Used in Observation 2 and Theorem 2.
standard math Subdividing an edge by a degree-2 node preserves treewidth in biconnected graphs with at least 4 nodes (Observation 2).
Proved in the paper; used in Theorem 2 to contract degree-2 nodes.
domain assumption A d-regular expander graph with node expansion 1/2 exists for d≥5 (Lubotzky [15], Lemma 3).
Used in Theorem 3 to construct high-treewidth level-k networks; depends on expander graph existence.
standard math Grohe-Marx lower bound: tw(G) ≥ floor(x_α(G)·(α/2)·|V(G)|) (Lemma 4).
Used in Theorem 3.
standard math Fomin-Høie bound: for subcubic graphs, tw(G) ≤ (1/6+ε)|V(G)| for large enough |V| (Lemma 2).
Used in Theorem 2.
standard math Lemma 1 (Coronado et al.): a biconnected graph H with m edges and n nodes requires level at least m-n+1, and any such H can be realized as a minor of a level-(m-n+1) network.
Re-proved in Section 3; central to both upper and lower bounds.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks." pith.science (2026). https://pith.science/paper/WJNCDZ4F

@misc{pith2026241113380,
  author       = {Pith},
  title        = {Pith review of: Bounds on the Treewidth of Level-k Rooted Phylogenetic Networks},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WJNCDZ4F}},
  note         = {Machine review of arXiv:2411.13380}
}

abstract

Phylogenetic networks are directed acyclic graphs that depict the genomic evolution of related taxa. Reticulation nodes in such networks (nodes with more than one parent) represent reticulate evolutionary events, such as recombination, reassortment, hybridization, or horizontal gene transfer. Typically, the complexity of a phylogenetic network is expressed in terms of its level, i.e., the maximum number of edges that are required to be removed from each biconnected component of the phylogenetic network to turn it into a tree. Here, we study the relationship between the level of a phylogenetic network and another popular graph complexity parameter - treewidth. We show a $\frac{k+3}{2}$ upper bound on the treewidth of level-$k$ phylogenetic networks and an improved $(1/3 + \delta) k$ upper bound for large $k$. These bounds imply that many computational problems on phylogenetic networks, such as the small parsimony problem or some variants of phylogenetic diversity maximization, are polynomial-time solvable on level-$k$ networks with constant $k$. Our first bound is applicable to any $k$, and it allows us to construct an explicit tree decomposition of width $\frac{k+3}{2}$ that can be used to analyze phylogenetic networks generated by tools like SNAQ that guarantee bounded network level. Finally, we show a $k/13$ lower bound on the maximum treewidth among level-$k$ phylogenetic networks for large enough $k$ based on expander graphs.

Figures

Figures reproduced from arXiv: 2411.13380 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 25 canonical work pages

[1]

Blair and C

C. Blair and C. An´ e. Phylogenetic trees and networks can serve as powerful and complementary approaches for analysis of genomic data. Systematic Biology, 69(3):593–601, 2020

work page 2020
[2]

H. L. Bodlaender. A tourist guide through treewidth. Acta cybernetica, 11(1-2):1–21, 1993

work page 1993
[3]

H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1–45, 1998

work page 1998
[4]

Bordewich, C

M. Bordewich, C. Semple, and K. Wicke. On the complexity of optimising variants of phylo- genetic diversity on phylogenetic networks. Theoretical Computer Science, 917:66–80, 2022

work page 2022
[5]

T. M. Coronado, J. C. Pons, and G. Riera. Counting cherry reduction sequences is counting linear extensions (in phylogenetic tree-child networks). arXiv preprint arXiv:2403.14491, 2024

work page Pith review arXiv 2024
[6]

Fischer, L

M. Fischer, L. Van Iersel, S. Kelk, and C. Scornavacca. On computing the maximum parsimony score of a phylogenetic network. SIAM Journal on Discrete Mathematics , 29(1):559–585, 2015

work page 2015
[7]

F. V. Fomin and K. Høie. Pathwidth of cubic graphs and exact algorithms. Information Processing Letters, 97(5):191–196, 2006

work page 2006
[8]

Grohe and D

M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B , 99(1):218–228, 2009

work page 2009

Show all 25 references

[9]

Holtgrefe, K

N. Holtgrefe, K. T. Huber, L. van Iersel, M. Jones, S. Martin, and V. Moulton. Squirrel: Re- constructing semi-directed phylogenetic level-1 networks from four-leaved networks or sequence alignments. bioRxiv, pages 2024–11, 2024. 6

2024
[10]

Janssen, M

R. Janssen, M. Jones, S. Kelk, G. Stamoulis, and T. Wu. Treewidth of display graphs: bounds, brambles and applications. Journal of Graph Algorithms and Applications , 23(4):715–743, 2019

2019
[11]

Kelleher, Y

J. Kelleher, Y. Wong, A. W. Wohns, C. Fadil, P. K. Albers, and G. McVean. Inferring whole- genome histories in large population datasets. Nature genetics, 51(9):1330–1338, 2019

2019
[12]

S. Kong, J. C. Pons, L. Kubatko, and K. Wicke. Classes of explicit phylogenetic networks and their biological and mathematical significance. Journal of Mathematical Biology, 84(6):47, 2022

2022
[13]

S. Kong, D. L. Swofford, and L. S. Kubatko. Inference of phylogenetic networks from sequence data using composite likelihood. Systematic Biology, page syae054, 2024

2024
[14]

A. L. Lewanski, M. C. Grundler, and G. S. Bradburd. The era of the arg: An introduction to ancestral recombination graphs and their significance in empirical evolutionary genomics. PLoS Genetics, 20(1):e1011110, 2024

2024
[15]

Lubotzky

A. Lubotzky. Discrete groups, expanding graphs and invariant measures, volume 125. Springer Science & Business Media, 1994

1994
[16]

Mirarab, L

S. Mirarab, L. Nakhleh, and T. Warnow. Multispecies coalescent: theory and applications in phylogenetics. Annual Review of Ecology, Evolution, and Systematics , 52(1):247–268, 2021

2021
[17]

Moulton and T

V. Moulton and T. Wu. Planar rooted phylogenetic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics , 20(2):1289–1297, 2022

2022
[18]

R. A. Pyron, K. A. O’Connell, E. A. Myers, D. A. Beamer, and H. Ba˜ nos. Complex hy- bridization in a clade of polytypic salamanders (plethodontidae: Desmognathus) uncovered by estimating higher-level phylogenetic networks. Systematic Biology, page syae060, 2024

2024
[19]

M. D. Rasmussen, M. J. Hubisz, I. Gronau, and A. Siepel. Genome-wide inference of ancestral recombination graphs. PLoS genetics, 10(5):e1004342, 2014

2014
[20]

Robertson and P

N. Robertson and P. D. Seymour. Graph minors. ii. algorithmic aspects of tree-width. Journal of algorithms , 7(3):309–322, 1986

1986
[21]

Scornavacca and M

C. Scornavacca and M. Weller. Treewidth-based algorithms for the small parsimony problem on networks. Algorithms for Molecular Biology , 17(1):15, 2022

2022
[22]

Sol ´ ıs-Lemus and C

C. Sol ´ ıs-Lemus and C. An´ e. Inferring phylogenetic networks with maximum pseudolikelihood under incomplete lineage sorting. PLoS genetics, 12(3):e1005896, 2016

2016
[23]

Sol ´ ıs-Lemus, P

C. Sol ´ ıs-Lemus, P. Bastide, and C. An´ e. Phylonetworks: a package for phylogenetic networks. Molecular biology and evolution , 34(12):3292–3298, 2017

2017
[24]

Van Iersel, M

L. Van Iersel, M. Jones, and M. Weller. Embedding phylogenetic trees in networks of low treewidth. Discrete Mathematics & Theoretical Computer Science , 25(Discrete Algorithms), 2023

2023
[25]

D. Wen, Y. Yu, J. Zhu, and L. Nakhleh. Inferring phylogenetic networks using phylonet. Systematic biology, 67(4):735–740, 2018. 7

2018

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

Blair and C

C. Blair and C. An´ e. Phylogenetic trees and networks can serve as powerful and complementary approaches for analysis of genomic data. Systematic Biology, 69(3):593–601, 2020

work page 2020

[2] [2]

H. L. Bodlaender. A tourist guide through treewidth. Acta cybernetica, 11(1-2):1–21, 1993

work page 1993

[3] [3]

H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical computer science, 209(1-2):1–45, 1998

work page 1998

[4] [4]

Bordewich, C

M. Bordewich, C. Semple, and K. Wicke. On the complexity of optimising variants of phylo- genetic diversity on phylogenetic networks. Theoretical Computer Science, 917:66–80, 2022

work page 2022

[5] [5]

T. M. Coronado, J. C. Pons, and G. Riera. Counting cherry reduction sequences is counting linear extensions (in phylogenetic tree-child networks). arXiv preprint arXiv:2403.14491, 2024

work page Pith review arXiv 2024

[6] [6]

Fischer, L

M. Fischer, L. Van Iersel, S. Kelk, and C. Scornavacca. On computing the maximum parsimony score of a phylogenetic network. SIAM Journal on Discrete Mathematics , 29(1):559–585, 2015

work page 2015

[7] [7]

F. V. Fomin and K. Høie. Pathwidth of cubic graphs and exact algorithms. Information Processing Letters, 97(5):191–196, 2006

work page 2006

[8] [8]

Grohe and D

M. Grohe and D. Marx. On tree width, bramble size, and expansion. Journal of Combinatorial Theory, Series B , 99(1):218–228, 2009

work page 2009