{"id":"b6b76e80-5d53-4a76-a90a-d5b32223b81f","arxiv_id":"2607.08259","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The ⊖-distances are metrics on rooted phylogenetic networks that extend Robinson-Foulds, admit poly-time algorithms on tree-child/normal/level-1/regular networks for the ancestry version, and reduce to Vertex Cover on distinct-cluster networks.","lead":"Two new distances compare phylogenetic networks by counting vertex removals that preserve ancestry. They extend the classic Robinson-Foulds tree metric, are true metrics, and are efficiently computable on many common network classes while remaining hard in general.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The manuscript cleanly introduces two operational distances, proves the metric axioms (Theorems 4.3–4.4), establishes the RF sandwich (Lemma 5.1), obtains polynomial-time algorithms on the classical network classes via a transparent multiset-cluster argument (Theorem 5.6), and supplies matching hardness and FPT/approximation results (Theorems 6.1, 7.8–7.11, 8.3). The only external dependencies are well-known uniqueness characterizations of semi-regular and regular networks; the paper re-proves the needed closure properties rather than merely citing them. Consequently the reader’s residual worry about “subtle edge cases” does not threaten any central claim. No experimental, parametric or circular constructions appear. The work is ready for acceptance as a solid combinatorial contribution; the verdict remains ACCEPT.","tokens_in":38368,"tokens_out":505,"duration_ms":5171,"concrete_test":"Independently re-derive the two directions of Proposition 5.5(i) for a non-binary PCC network that contains a vertex of out-degree 1 and a non-trivial shortcut; confirm that (N⊖W)^- remains PCC and that equal cluster multisets still force N^- ≃ (N')^-. If both directions hold, the poly-time claims of Theorem 5.6 stand.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's weakest-assumption flag (possible edge cases in the Hellmuth et al. 2023 characterizations of PCC/semi-regular/regular networks that underwrite Proposition 5.5 and Theorem 5.6) does not appear load-bearing. Proposition 5.5 re-proves ⊖-shortcut-closedness and multicluster-shortcut-encodedness directly from the definitions given in the present paper (preservation of clusters and ancestor relations under ⊖ and shortcut removal, Lemmas 2.1 and 3.2) together with the uniqueness statements already cited from [23]. The poly-time claims for the listed classes therefore rest only on those internal arguments plus the elementary observation that trees, tree-child, normal and level-1 networks satisfy PCC; they do not inherit any unexamined edge cases. All other central claims (metric axioms, RF lower bounds, hardness reductions, Vertex-Cover equivalence) are self-contained and standard.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces two operational distances on rooted phylogenetic networks based on the ⊖-operator (vertex deletion that reconnects parents to children while preserving ancestry). d_⊖ is the minimum total number of internal vertices that must be removed from two networks so that the resulting networks are leaf-fixing isomorphic; d_⊖^- requires only that the shortcut-free reductions are isomorphic. Theorems 4.3 and 4.4 establish that these are metrics up to the respective equivalence relations. Both distances extend the Robinson–Foulds distance on trees and are bounded below by the hardwired (multi)cluster distances (Lemma 5.1). For networks satisfying PCC (hence tree-child, normal, level-1, semi-regular and regular networks) d_⊖^- equals the multiset cluster distance and is therefore polynomial-time computable (Theorem 5.6). Computing d_⊖ is NP-hard, W[2]-hard and inapproximable even on DC-similar tree-child networks (Theorem 6.1). Computing d_⊖^- is NP-hard in general (Theorem 8.3) but, on distinct-cluster networks, reduces to Vertex Cover on the bad-ancestry graph, yielding FPT and 2-approximation algorithms (Theorems 7.8–7.11).","tokens_in":38608,"tokens_out":784,"duration_ms":6958,"significance":"The work supplies genuine metrics (rather than pseudometrics) that apply to arbitrary rooted phylogenetic networks, recover the classical Robinson–Foulds distance on trees, and admit a transparent operational interpretation via common ancestry cores. The algorithmic dichotomy is clean: d_⊖^- is tractable on the most commonly studied network classes and reduces to a well-studied combinatorial problem on distinct-cluster networks, while d_⊖ is hard even on those classes. All central claims are accompanied by complete, self-contained proofs; the Vertex-Cover formulation immediately supplies practical exact, FPT and approximation methods. The contribution is therefore both theoretically solid and of direct utility for network comparison in computational phylogenetics.","major_comments":[],"minor_comments":[{"comment":"Throughout: several typographical slips remain (e.g. “retriculation”, “shotcut-removal”, “bypassing sets” used before Definition 7.1 is fully motivated). A careful copy-edit would improve readability.","section":"global"},{"comment":"Figure 1 caption and surrounding text: the concrete numerical example (d_⊖=3, d_⊖^-=1) is helpful; adding the corresponding cluster multisets would make the lower-bound relation of Lemma 5.1 immediately visible.","section":"Figure 1"},{"comment":"Section 9: the open questions on c-distinct-cluster networks and on the realizability of arbitrary graphs as bad-ancestry graphs are well-posed; a one-sentence pointer to the corresponding complexity status of coloured isomorphism would help the reader.","section":"§9"},{"comment":"References: a few arXiv preprints are cited without final publication data (e.g. [24]); update where possible.","section":"References"}],"recommendation":"accept","confidential_remarks":"The manuscript is ready for acceptance. The only potential external dependency flagged by the reader (characterizations of PCC/semi-regular networks from Hellmuth et al. 2023) is re-proved internally in Proposition 5.5 from the paper’s own lemmas; no load-bearing gap remains. Fit for a discrete-mathematics / computational-biology venue is excellent."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is a clean combinatorial paper that does what it claims. Hellmuth, Lafond and Scholz take the existing ⊖-operator (vertex deletion that rewires parents to children while preserving ancestry) and turn it into two genuine distances: d_⊖ (full isomorphism after deletions) and d_⊖^- (isomorphism after also stripping shortcuts). Both satisfy the metric axioms up to the natural equivalences, both lower-bound the hardwired cluster distances, and both collapse exactly to Robinson–Foulds on trees. That package is new and useful.\n\nWhat they do well is the complexity dichotomy. On the classes people actually use—tree-child, normal, level-1, regular, PCC—d_⊖^- equals the multiset cluster distance and is therefore polynomial. The argument is self-contained: they prove the classes are ⊖-shortcut-closed and multicluster-shortcut-encoded from the definitions and the usual uniqueness lemmas, so the earlier characterizations are not a hidden load-bearing assumption. Meanwhile d_⊖ is NP-hard, W[2]-hard and inapproximable even on DC-similar tree-child networks (Set Cover reduction). For distinct-cluster networks the ancestry distance reduces cleanly to Vertex Cover on the bad-ancestry graph, giving FPT and a 2-approximation. All the proofs are written out; the reductions are standard and tight.\n\nSoft spots are minor. There are no experiments, so we do not yet know how the distances behave on real reconstructed networks or how large the bad-ancestry graphs get in practice. The outlook section flags several natural open questions (c-distinct-cluster FPT, which graphs arise as bad-ancestry graphs, level-parameterized complexity) that the paper itself does not settle. None of that undercuts the theorems.\n\nThis is for people who work on phylogenetic network comparison or operational distances on DAGs. A serious referee will find the math solid and the contribution clear. I would send it out.","headline":"Clean operational metrics that actually work as metrics, extend RF, and come with a sharp complexity split; solid combinatorial paper ready for referees.","tokens_in":39196,"tokens_out":499,"would_cite":true,"duration_ms":6454,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C85","68Q25","92B10","05C90"],"pacs":[],"model":"grok-4.5","headline":"Two new distances compare phylogenetic networks by counting vertex removals that leave isomorphic ancestry structure.","keywords":["phylogenetic networks","network comparison","operational distance","Robinson-Foulds distance","hardwired clusters","shortcut-free networks","distinct-cluster networks","vertex cover"],"falsifier":"Exhibit two networks inside one of the listed classes that have identical cluster multisets yet non-isomorphic shortcut-free versions, or two DC-similar networks whose minimum bypassing set is strictly smaller than twice the size of a minimum vertex cover of their bad-ancestry graph.","tokens_in":39291,"feed_emoji":"🌳","tokens_out":713,"duration_ms":6080,"temperature":0.7,"pith_summary":"Phylogenetic networks describe evolutionary histories with reticulation, but comparing them is hard: feature-based scores often fail to be true metrics, and most operational distances are restricted or NP-hard. This paper defines two distances from the ⊖-operator, which deletes a vertex and reconnects its parents to its children while preserving ancestor relations among the survivors. The distance d_⊖ is the fewest total internal vertices that must be removed from both networks until the results are leaf-fixing isomorphic; the relaxed distance d_⊖^- ignores shortcut arcs and therefore compares only the induced ancestry. Both are genuine metrics (up to the natural equivalences), both recover the classical Robinson–Foulds distance on trees, and both are bounded below by hardwired cluster distances. On broad practical classes—tree-child, normal, level-1, regular—d_⊖^- equals the multiset cluster distance and can be computed in polynomial time; d_⊖ remains hard even on those classes. For distinct-cluster networks the computation of d_⊖^- reduces exactly to Vertex Cover, giving FPT algorithms and a 2-approximation. Optimal deletion sets also serve as interpretable witnesses that localize which vertices and ancestry relations differ.","feed_headline":"New network distances count vertex removals to match ancestry","feed_subtitle":"They recover Robinson–Foulds on trees and are poly-time on tree-child and regular networks","key_machinery":"The ⊖-operator (remove a vertex and join every parent to every child) together with the bad-ancestry graph of two DC-similar networks, whose minimum vertex covers are exactly the minimum bypassing sets that realize d_⊖^-.","core_discovery":"The ⊖-operator yields two operational distances that are true metrics on rooted phylogenetic networks (up to leaf-fixing isomorphism for d_⊖ and shortcut-free isomorphism for d_⊖^-), both extend Robinson–Foulds, and d_⊖^- is polynomial-time computable on the main network classes used in practice while reducing to Vertex Cover on distinct-cluster networks.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["⊖-operator distances count vertex removals to match network ancestry","Two metrics via vertex deletion extend Robinson–Foulds to phylogenetic networks","d_⊖ and d_⊖^- turn ancestry-preserving removals into true network metrics","Polynomial ⊖^- distance on tree-child and regular networks; NP-hard in general","Vertex-removal metrics recover RF on trees and reduce to Vertex Cover"],"cache_read_input_tokens":32896,"weakest_assumption_plain":"The claim that d_⊖^- equals the multiset cluster distance on tree-child, normal, level-1 and regular networks rests on those classes being both closed under shortcut-free ⊖-reduction and uniquely determined by their cluster multisets.","fun_headline_variants_meta":{"raw":{"variants":["⊖-operator distances count vertex removals to match network ancestry","Two metrics via vertex deletion extend Robinson–Foulds to phylogenetic networks","d_⊖ and d_⊖^- turn ancestry-preserving removals into true network metrics","Polynomial ⊖^- distance on tree-child and regular networks; NP-hard in general","Vertex-removal metrics recover RF on trees and reduce to Vertex Cover"]},"model":"grok-4.5","effort":"low","cost_usd":0.00322,"raw_usage":{"total_tokens":1128,"prompt_tokens":791,"num_sources_used":0,"completion_tokens":103,"cost_in_usd_ticks":32200000,"prompt_tokens_details":{"text_tokens":791,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":234,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":791,"tokens_out":103,"duration_ms":3346,"temperature":1.0,"reasoning_tokens":234,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T10:27:35.125828+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit two networks inside one of the listed classes that have identical cluster multisets yet non-isomorphic shortcut-free versions, or two DC-similar networks whose minimum bypassing set is strictly smaller than twice the size of a minimum vertex cover of their bad-ancestry graph.","supporting_citations":[],"review_version":1}