{"id":"1d31a18e-0a12-4e99-b09c-ff41d4463a04","arxiv_id":"2502.08746","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A graph is explainable by a level-1 phylogenetic network if and only if every primitive induced subgraph is a near-cograph, and such graphs can be recognized in linear time.","lead":"This paper characterizes which gene orthology graphs can be explained by simple level-1 evolutionary networks. It shows these are exactly the graphs whose primitive building blocks are near-cographs, and it gives a linear-time algorithm for recognizing and constructing them.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The primitive-case reduction (Lemma 4.7) is load-bearing and depends on imported structural characterizations (Thm 2.12 from [47], Thm 3.6 via [42]); the central characterization inherits all risk from these external results.","rationale":"The central claim is the iff in Theorem 4.20. The proof is a chain reducing to the primitive case, and the primitive case rests on Lemma 4.7. That lemma's two pivotal moves are (a) replacing an arbitrary explaining level-1 network by a regular 2-lca-relevant one, and (b) using closed+(L) to ensure the Hasse diagram is a level-1 network. Both moves are imported: Theorem 3.6 cites [42, Thm 3.12], and Theorem 2.12 cites [47]. Neither is re-proven or machine-checked here. The paper also flags that its level-1 definition is more general than customary, so even if the imports are correct for this definition, transfer to standard level-1 networks is not automatic. This is a scope/correctness risk rather than an internal inconsistency. The reader's weakest_assumption identifies the same point, and the proposed brute-force test would settle it. I would keep the CONDITIONAL verdict rather than accepting unconditionally or rejecting.","tokens_in":37744,"tokens_out":49733,"duration_ms":482171,"concrete_test":"For |X|<=6, do two exhaustive checks. (1) Enumerate all grounded set systems C on X that are closed and satisfy (L); confirm that H(C) is a regular, 2-lca-relevant phylogenetic level-1 network realizing exactly C; and enumerate all small level-1 networks and confirm their cluster systems satisfy closed+(L). (2) For every small level-1 network N and 0/1 labeling t, compute G(N,t), build C({1,2}) as in Theorem 3.6, recompute H(C({1,2})), and verify that it is regular level-1, has the same lca(x,y) for all pairs, and explains G(N,t). If either check fails, Theorem 4.20 needs revision; if both pass, the imported load is validated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The road from the main characterization to the key primitive case goes: Theorem 4.20, then Theorem 4.19, then Theorem 4.12, then Lemma 4.7. Lemma 4.7 assumes that any level-1 explainable graph G can be explained by a regular, 2-lca-relevant level-1 network (Theorem 3.6, whose proof invokes [42, Thm 3.12]), and that level-1 network cluster systems are exactly closed systems satisfying property (L) (Theorem 2.12, imported from [47]). These two imports are used to force a single hybrid whose cluster is a singleton, making G-h a cograph. Neither is proved in this manuscript, neither is machine-checked, and the paper's Definition 2.2 deliberately generalizes the customary level-1 notion by allowing hybrid leaves. If Theorem 3.6 or Theorem 2.12 is false, or applies only under a different definition, the proof of Theorem 4.12 collapses and Theorems 4.19/4.20, the central equivalence, are unsupported. The manuscript explicitly notes the generalized definition but does not state whether the characterization transfers to stricter standard level-1 network classes. This is a correctness and scope risk, not an inconsistency within the paper's own definitions.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies graphs that can be explained by 0/1-labeled phylogenetic level-1 networks (LEV-1-EX graphs), motivated by orthology graphs. The central result is Theorem 4.20: a graph is LEV-1-EX if and only if every primitive induced subgraph is a near-cograph. Equivalent characterizations are also given in terms of prime quotient graphs being near-cographs (Theorem 4.19), phylogenetic level-1 explainability (Theorem 4.21), and closure under substitution and atomic expressions (Theorems 4.24 and 4.26). The paper further shows that every graph is explainable by some level-k network with k < |X| (Theorem 3.10), provides a linear-time recognition and construction algorithm (Theorem 4.22), and proves that LEV-1-EX graphs are weakly chordal, perfect, and of twin-width at most 2 (Theorem 4.29 and Proposition 4.30).","tokens_in":37975,"tokens_out":20036,"duration_ms":166692,"significance":"If the result holds, this is a substantial contribution to the theory of orthology graphs under network-like evolution: it extends the tree/cograph characterization to the level-1 network setting in a clean, modular-decomposition way. The proof structure is transparent, with the primitive case (Theorem 4.12) proved by explicit network constructions and then lifted to arbitrary graphs via prime-vertex replacement networks. The linear-time algorithm is a concrete algorithmic payoff, and the graph-class consequences (weakly chordal, perfect, twin-width at most 2) give falsifiable structural predictions. The main caveat is that the primitive-case reduction relies on imported structural characterizations of level-1 networks from [42] and [47]; within the paper's own definitional framework the derivation is coherent, and no circularity was found.","major_comments":[{"comment":"Lemma 4.7, which is load-bearing for the central characterization, assumes that an arbitrary level-1 explainable graph can be represented by a regular, 2-lca-relevant level-1 network (Theorem 3.6, via [42, Thm. 3.12]) and that level-1 network cluster systems are exactly the closed systems satisfying property (L) (Theorem 2.12, imported from [47]). Since Definition 2.2 deliberately generalizes the customary notion of level-1 networks by allowing hybrid leaves, the paper should state explicitly that Theorem 2.12 and the level-1 results of [47] are valid for this generalized class, or else prove the needed direction for hybrid leaves. As written, the conclusion of Lemma 4.7 that the unique hybrid can be taken to be a leaf, and therefore Theorems 4.19 and 4.20, inherits this external assumption; the transfer to the stricter standard level-1 class is not established. This is a scope and correctness clarification rather than an internal contradiction, but it is load-bearing and should be addressed in the revision.","section":"§2, Definition 2.2; §3.2, Theorem 3.6; §4.2, Lemma 4.7"}],"minor_comments":[{"comment":"The abbreviation LEV-k-EX is used starting from Theorem 3.10 and throughout Section 4, but it appears not to be formally defined; please add a definition near Definition 3.1 or at the first use of LEV-k-EX.","section":"§3.2, Theorem 3.10 and thereafter"},{"comment":"The final sentence of the proof reads 'In summary, can be verified in O(|X|+|E|) time'; the subject 'it' is missing and should be restored.","section":"§4.4, Theorem 4.22 proof"},{"comment":"In the definition of series and parallel strong modules, the text appears to print 'G[M] is disconnected' in both cases; the series case should refer to the complement graph, so please check the typesetting of the overline.","section":"§4.1, modular decomposition"},{"comment":"The condition for two networks to be internal vertex-disjoint should be that the displayed intersection is empty; the printed '=/0' is easy to misread as nonempty and should be typeset unambiguously as the empty set.","section":"§4.3, Definition 4.15"}],"recommendation":"major_revision","confidential_remarks":"The paper relies heavily on prior results by the same research group ([42], [47], [58]). This is not itself a defect, but the editor may wish to confirm that the novelty with respect to those papers is sufficiently delineated, since Theorems 3.6, 4.12, 4.19, 4.20, and Algorithm 1 all depend on those imports."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The short version: this paper gives a genuinely useful graph-theoretic characterization of level-1 explainable orthology graphs — all primitive induced subgraphs are near-cographs — and backs it with a linear-time recognition and construction algorithm. The characterization is elegant and the modular-decomposition framing is the right tool. The proof of the main theorem is detailed and the constructions are explicit. I think the central claim is likely correct.\n\nWhat's new and good: the equivalence of LEV-1-EX with the near-cograph condition on primitive induced subgraphs (Theorem 4.20), the quotient formulation (4.19), the substitution closure (4.24–4.26), and the connections to weakly chordal and perfect graphs and twin-width ≤ 2 (4.29, 4.30). The linear-time algorithm is a solid byproduct and the runtime argument for the sum of quotient edges is careful and clever.\n\nThe soft spots are real but not fatal. First, the proof of the primitive case (Lemma 4.7) rests on two imported structural theorems: Theorem 2.12 from [47] (level-1 networks correspond to closed clustering systems satisfying property (L)) and Theorem 3.6 via [42, Thm. 3.12] (regular 2-lca-relevant reduction). Both are stated as known results and neither is re-proved here. That is fine in normal mathematical practice, but it means the characterization inherits exactly what those theorems assume. Second, Definition 2.2 deliberately allows hybrid leaves, which is more permissive than the standard level-1 definition in part of the phylogenetics literature. The authors never state whether the characterization transfers to the stricter setting. If you work with the standard definition, you have to check that the imported theorems hold there too. This is a scope question, not an internal inconsistency. Third, there is a small typo in Definition 4.15 (the 'internal vertex-disjoint' condition reads '≠ ∅' where it must be '= ∅'); it is obvious and harmless, but worth fixing.\n\nI would send it to review. The referee should ask for a clear statement about the definitional scope and for the dependencies on [42],[47] to be spelled out, but the core contribution is substantive and the proofs are at a level that deserves referee time rather than desk rejection.","headline":"A clean, carefully argued characterization of level-1 explainable orthology graphs, with a linear-time algorithm; the main caveat is that the proof leans on imported theorems and a slightly nonstandard definition of level-1.","tokens_in":38547,"tokens_out":2873,"would_cite":true,"duration_ms":26491,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","05C75","92D15"],"pacs":[],"model":"deepseek-v4-flash","headline":"A graph is level-1 explainable if and only if every primitive induced subgraph is a near-cograph.","keywords":["orthology graph","level-1 network","near-cograph","modular decomposition","phylogenetic network","twin-width","perfect graph","linear-time algorithm"],"falsifier":"Take the 5-cycle $C_5$: deleting any one vertex leaves a path on four vertices, which is not a cograph, so $C_5$ is primitive and not a near-cograph; the theorem predicts that no level-1 network with speciation labels can explain it. Finding such a network would refute the central claim.","tokens_in":37498,"feed_emoji":"🧬","tokens_out":11209,"duration_ms":88859,"temperature":0.7,"pith_summary":"Orthology graphs inferred under a tree-like model must be cographs, but real data often are not, and network-like evolution is a natural explanation. This paper establishes that the graphs explainable by a level-1 phylogenetic network—one where each biconnected block contains at most one reticulation—are exactly the graphs whose primitive induced subgraphs are near-cographs, meaning deletion of a single vertex leaves a cograph. The same class is characterized via modular decomposition (all non-trivial prime quotients must be near-cographs) and via closure under disjoint union, join, and vertex substitution, and it can be recognized and realized by a network in linear time. So the paper converts a question about evolutionary feasibility into a structural graph problem, showing that level-1 reticulation relaxes the cograph condition in a precise, algorithmically tractable way.","feed_headline":"Level-1 networks explain exactly the near-cograph graphs","feed_subtitle":"Orthology data that resist tree-like models get a precise structure: remove one vertex, get a cograph.","key_machinery":"The machinery is modular decomposition together with prime-vertex replacement: the modular decomposition tree of $G$ organizes the strong modules into series, parallel, and prime nodes, and each prime module $M$ is represented by its quotient graph $G[M]/M_{\\max}(G[M])$. The key step is Theorem 4.12, which shows that a primitive graph is level-1 explainable exactly when it is a primitive near-cograph; the proof reduces a primitive level-1 network to a regular, 2-lca-relevant network (one in which every vertex is a least common ancestor of some one- or two-leaf set) with a single hybrid leaf, and then removes that leaf to obtain a cotree. Near-cographs are the atomic graphs: a graph from which one vertex deletion gives a cograph, where a cograph is a graph with no induced $P_4$ built from disjoint unions and joins. Prime-vertex replacement networks then assemble a level-1 network for the whole graph by substituting each prime quotient with such an atomic network inside the modular decomposition tree.","core_discovery":"The paper's central claim is Theorem 4.20: a graph $G$ is level-1 explainable if and only if every primitive induced subgraph of $G$ is a near-cograph. A near-cograph is a graph from which removing one vertex yields a cograph, and a cograph is a graph with no induced path on four vertices ($P_4$). The characterization is shown to be equivalent to the statement that, for every non-trivial prime module $M$ of the modular decomposition, the quotient graph $G[M]/M_{\\max}(G[M])$ is a near-cograph (Theorem 4.19), and to the statement that $G$ can be built from single vertices and primitive near-cographs using disjoint unions, joins, and vertex substitution (Theorems 4.24 and 4.26). The paper further proves that level-1 explainable graphs are weakly chordal and hence perfect, and that they have twin-width at most 2, so algorithmic tools for those graph classes apply to them.","pith_inferences":["Editorial inference: since every graph is explainable at some level, the biologically meaningful boundary is the number of reticulation events per block; level-1 is the only level that still yields a non-trivial graph class, so comparing inferred orthology graphs against this class can serve as a test for 'almost tree-like' evolution.","Editorial inference: the characterization suggests a new editing problem—turn an input orthology graph into the nearest level-1 explainable graph—whose complexity the paper leaves open; such an algorithm would be a network-aware alternative to cograph editing for data cleaning.","Editorial inference: the modular-decomposition-plus-replacement strategy is a plausible template for level-2 and higher networks, but the paper's Figure 5 shows that a second hybrid can change the primitive graphs substantially, so a level-2 characterization would require genuinely new structural control rather than a routine extension."],"forward_implications":["Every graph is level-$k$ explainable for some $k<|X|$, so for large $k$ the network model imposes no structural restriction; the level-1 condition is where a meaningful, testable constraint appears.","Any graph containing an induced cycle or anti-cycle on $n\\ge 5$ vertices is not level-1 explainable, since such subgraphs are primitive and not near-cographs.","The class of level-1 explainable graphs is hereditary and closed under disjoint unions, joins, and vertex substitution, giving a recursive grammar whose atoms are single vertices and primitive near-cographs.","There is an $O(|X|+|E|)$-time algorithm that recognizes level-1 explainable graphs and, if possible, constructs an explaining level-1 network.","Level-1 explainable graphs are weakly chordal, perfect, and have twin-width at most 2, placing them in known algorithmic regimes."],"supporting_citations":[{"why":"supplies the closed-and-(L) cluster characterization of level-1 networks (Theorem 2.12) used throughout the proofs.","marker":"[47]"},{"why":"provides the regular 2-lca-relevant reduction (Theorem 3.6) that lets the primitive case assume a single hybrid.","marker":"[42]"},{"why":"supplies the prime-vertex replacement network construction and the induced-subgraph network restriction (Proposition 3.5).","marker":"[58]"},{"why":"establishes that tree-explainable orthology graphs are exactly cographs, the baseline being relaxed here.","marker":"[45]"},{"why":"gives the linear-time cograph recognition routine used to test near-cograph quotients in Algorithm 1.","marker":"[14]"},{"why":"provides the modular decomposition framework and its linear-time computation used to build quotients.","marker":"[40]"},{"why":"proves that primitive graphs contain an induced P4, a fact used in the primitive-case arguments.","marker":"[73]"},{"why":"supplies the lemma that induced primitive subgraphs embed into prime quotient graphs, used for Theorem 4.20.","marker":"[44]"}],"fun_headline_variants":["Near-cographs define level-1 explainable orthology graphs","Level-1 networks explained by near-cograph primitive subgraphs","Orthology graphs: level-1 iff near-cograph prime modules","Level-1 explainability reduces to near-cograph characterization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that any level-1 explainable graph can be explained by a regular level-1 network whose clusters faithfully encode all pairwise least common ancestors, and that level-1 networks are exactly those whose cluster systems are closed and satisfy the technical property (L); if these imported equivalences fail, or hold only for the generalized level-1 definition that allows hybrid leaves, the near-cograph criterion may not transfer to standard networks.","fun_headline_variants_meta":{"raw":{"variants":["Near-cographs define level-1 explainable orthology graphs","Level-1 networks explained by near-cograph primitive subgraphs","Orthology graphs: level-1 iff near-cograph prime modules","Level-1 explainability reduces to near-cograph characterization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000182,"raw_usage":{"total_tokens":1375,"prompt_tokens":1075,"completion_tokens":300,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":691,"completion_tokens_details":{"reasoning_tokens":229}},"tokens_in":691,"tokens_out":300,"duration_ms":4126,"temperature":1.0,"reasoning_tokens":229,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T23:49:59.219328+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the 5-cycle $C_5$: deleting any one vertex leaves a path on four vertices, which is not a cograph, so $C_5$ is primitive and not a near-cograph; the theorem predicts that no level-1 network with speciation labels can explain it. Finding such a network would refute the central claim.","supporting_citations":[{"cited_title":"Discrete Mathematics 6(3):281–298, DOI 10.1016/0012-365X(73)90100-3","cited_arxiv_id":null,"evidence_quote":"proves that primitive graphs contain an induced P4, a fact used in the primitive-case arguments."},{"cited_title":"Network Representation and Modular Decomposition of Combinatorial Structures: A Galled-Tree Perspective","cited_arxiv_id":"2406.18713","evidence_quote":"supplies the prime-vertex replacement network construction and the induced-subgraph network restriction (Proposition 3.5)."},{"cited_title":"SIAM Journal on Computing 14(4):926–934, DOI 10.1137/0214065","cited_arxiv_id":null,"evidence_quote":"gives the linear-time cograph recognition routine used to test near-cograph quotients in Algorithm 1."},{"cited_title":"Computer Science Review 4(1):41–59, DOI 10.1016/j.cosrev.2010.01.001","cited_arxiv_id":null,"evidence_quote":"provides the modular decomposition framework and its linear-time computation used to build quotients."},{"cited_title":"Discrete Applied Mathematics 343:25–43, DOI 10.1016/j.dam.2023.09.034","cited_arxiv_id":null,"evidence_quote":"supplies the lemma that induced primitive subgraphs embed into prime quotient graphs, used for Theorem 4.20."}],"review_version":1}