{"id":"263351e5-80ff-4905-a62d-460ff0251e2d","arxiv_id":"2411.13380","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For level-k phylogenetic networks, the paper proves treewidth is at most (k+3)/2, improves this to about k/3 for large k, and shows some level-k networks have treewidth at least k/13.","lead":"Phylogenetic networks are graphs of evolutionary history; this paper proves tighter upper and lower bounds on their treewidth, a measure of how close they are to a tree. The bounds mean many hard computational problems on these networks become more tractable for networks with bounded complexity.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's induction invokes Lemma 1 on the graph G' left after deleting a degree-3 vertex, but Lemma 1 requires biconnectivity and G' need not be biconnected; the step is unproved as written, though repairable by a block decomposition.","rationale":"The reader's weakest_assumption identifies exactly the same load-bearing concern: the induction step of Theorem 1 cites Lemma 1 for a graph G' that is only guaranteed to be connected, not biconnected. This is the most serious issue in the paper because Theorem 1 is the first main upper bound and the basis for the explicit tree decomposition mentioned in the abstract. The gap is real and appears in the text: 'By Lemma 1, we can turn G' into a directed network M' with level k' = |E(G')| - |V(G')| + 1...' is not justified by Lemma 1 as stated. The concern is repairable through a block decomposition of G', since the cyclomatic number of each block is bounded by that of G', which is at most k-2; applying the induction hypothesis per block and then adding the deleted vertex gives the claimed bound. Because the fix is straightforward and the other two theorems (the asymptotic (1/3+2epsilon)k upper bound and the k/13 lower bound) are substantially supported by the cited results and the presented computations, the appropriate verdict is conditional acceptance rather than rejection. I agree with the reader's conditional verdict, so no change to the verdict is needed.","tokens_in":6765,"tokens_out":23753,"duration_ms":249994,"concrete_test":"Repair the induction in Theorem 1 by applying Lemma 1 to each biconnected block of G' rather than to G' itself, and verify that every block has cyclomatic number at most k-2; then confirm tw(M) <= max_B tw(B)+1 <= (k+3)/2. A minimal test case is a theta graph with three internally disjoint paths and k=2: deleting a degree-3 vertex yields a non-biconnected G', so the published argument cannot invoke Lemma 1, whereas the block-decomposition repair gives tw(M) <= 2. If the repair fails on any level-k biconnected component, the upper bound itself would be false.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 1 (Section 4) contains the following step: after deleting a degree-3 or higher node v from the maximum-treewidth biconnected component M, the remaining graph G' is turned into a directed network M' via Lemma 1, with level k' = |E(G')|-|V(G')|+1 <= k-2. Lemma 1, however, applies only to biconnected graphs H, and G' need not be biconnected. For example, if M is a theta graph (two degree-3 vertices joined by three internally disjoint paths), deleting one of the two degree-3 vertices leaves a graph whose biconnected blocks are single edges or paths, so G' is not biconnected. Consequently, Lemma 1's existence and level guarantee does not directly apply. Moreover, the asserted equality k' = |E(G')|-|V(G')|+1 is generally false for non-biconnected G': when a connected graph is realized by subdividing its non-tree edges, its level is the maximum cyclomatic number over its biconnected blocks, not the total cyclomatic number |E(G')|-|V(G')|+1. This missing justification is load-bearing because it is the only argument bounding tw(M') in the induction. 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 a level-(k-2) network containing that block as a minor, and use tw(G') = max over blocks. But as written, the proof of the paper's first main upper bound is incomplete.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":7067,"tokens_out":22287,"duration_ms":230672,"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":[{"comment":"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":"Section 4, proof of Theorem 1"},{"comment":"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":"Section 4, Theorem 2"},{"comment":"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.","section":"Section 5, Theorem 3"}],"minor_comments":[{"comment":"There is a typo: 'levek-k' should be 'level-k'.","section":"Section 4, opening sentence"},{"comment":"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":"Abstract and Section 4"},{"comment":"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.","section":"Section 2, Observation 2"}],"recommendation":"major_revision","confidential_remarks":"The main gap identified in Theorem 1 is exactly where the first upper-bound claim hinges; I believe it is repairable by the block-decomposition argument described above. The lower-bound theorem also needs a covering argument to justify 'for large k'. The paper is publishable in principle after these repairs, and I do not see circularity or unsupported external claims beyond the issues listed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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.\n\nOne 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.\n\nThis 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.","headline":"Genuinely new bounds on treewidth of level-k phylogenetic networks, with a real but repairable gap in the proof of the main upper bound.","tokens_in":7710,"tokens_out":8791,"would_cite":true,"duration_ms":87100,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C83","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Level-k networks have treewidth at most (k+3)/2","keywords":["phylogenetic networks","treewidth","level-k networks","reticulation number","graph minors","tree decomposition","expander graphs","small parsimony"],"falsifier":"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.","tokens_in":6490,"feed_emoji":"🧬","tokens_out":7602,"duration_ms":67260,"temperature":0.7,"pith_summary":"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.","feed_headline":"Level-k networks have treewidth at most (k+3)/2","feed_subtitle":"Upper and lower bounds show treewidth scales with reticulation level, enabling faster algorithms.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Establishes the minor–level correspondence (Lemma 1) that converts level bounds into edge/node counts of biconnected minors; used in both upper-bound proofs and the lower-bound construction.","marker":"[5]"},{"why":"Provides the k+1 upper bound that serves as the base case for k≤1 and the starting point for the paper's tighter bounds.","marker":"[10]"},{"why":"Supplies the standard fact that treewidth of a graph is the maximum treewidth of its biconnected components, letting the proof restrict to a single component.","marker":"[3]"},{"why":"Gives the subcubic treewidth bound in terms of vertex count that yields the (1/3+2ε)k upper bound for large k.","marker":"[7]"},{"why":"Relates treewidth to node expansion, the bridge that turns expander graphs into a treewidth lower bound in Theorem 3.","marker":"[8]"},{"why":"Guarantees the existence of 5-regular expander graphs with node expansion 1/2, which the lower-bound construction reshapes into level-k networks.","marker":"[15]"}],"fun_headline_variants":["Treewidth of level-k networks: at most (k+3)/2","Level-k networks: treewidth between k/13 and (k+3)/2","Phylogenetic level bounds treewidth, enabling fast algorithms","Treewidth scales with reticulation level in networks","New bounds link treewidth and level in phylogenetic networks"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Treewidth of level-k networks: at most (k+3)/2","Level-k networks: treewidth between k/13 and (k+3)/2","Phylogenetic level bounds treewidth, enabling fast algorithms","Treewidth scales with reticulation level in networks","New bounds link treewidth and level in phylogenetic networks"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000754,"raw_usage":{"total_tokens":3379,"prompt_tokens":995,"completion_tokens":2384,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":611,"completion_tokens_details":{"reasoning_tokens":2296}},"tokens_in":611,"tokens_out":2384,"duration_ms":16089,"temperature":1.0,"reasoning_tokens":2296,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T16:31:12.102232+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Counting cherry reduction sequences is counting linear extensions (in phylogenetic tree-child networks)","cited_arxiv_id":"2403.14491","evidence_quote":"Establishes the minor–level correspondence (Lemma 1) that converts level bounds into edge/node counts of biconnected minors; used in both upper-bound proofs and the lower-bound construction."},{"cited_title":"Janssen, M","cited_arxiv_id":null,"evidence_quote":"Provides the k+1 upper bound that serves as the base case for k≤1 and the starting point for the paper's tighter bounds."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the standard fact that treewidth of a graph is the maximum treewidth of its biconnected components, letting the proof restrict to a single component."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the subcubic treewidth bound in terms of vertex count that yields the (1/3+2ε)k upper bound for large k."},{"cited_title":"Grohe and D","cited_arxiv_id":null,"evidence_quote":"Relates treewidth to node expansion, the bridge that turns expander graphs into a treewidth lower bound in Theorem 3."},{"cited_title":"Lubotzky","cited_arxiv_id":null,"evidence_quote":"Guarantees the existence of 5-regular expander graphs with node expansion 1/2, which the lower-bound construction reshapes into level-k networks."}],"review_version":1}