{"id":"d209e9bf-e57f-48cb-a972-f2c063ba682d","arxiv_id":"2502.08251","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Labelled arboreal networks explain exactly the distance-hereditary graphs.","lead":"This paper proves that the graphs representable by labelled arboreal networks, a multi-rooted generalization of rooted trees, are exactly the distance-hereditary graphs. It also gives an algorithm that builds such a network for every distance-hereditary graph and characterizes the two-root case.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the only unproved step in Theorem 4 is the cited tree fact, and it is true by a standard longest-path argument, so the induction survives scrutiny.","rationale":"The reader's ACCEPT verdict is sound. The converse direction of Theorem 4 rests on an unstated but elementary tree fact; once supplied, the long-path argument removes the only candidate weakness. The forward direction via Algorithm 1 carries a complete induction with all cases verified. Sections 6 and 7 depend on previously published characterizations, and their internal case analyses appear coherent. No data, parameters, or computational claims are overreached. The only real issue spotted is the c3 typo, which is local, easily corrected, and does not affect the central equivalence between arboreal-explainable graphs and distance-hereditary graphs.","tokens_in":34352,"tokens_out":18344,"duration_ms":192704,"concrete_test":"State and prove the missing tree lemma: in a tree with no degree-2 vertices and at least five leaves, a longest leaf-to-leaf path gives a neighbor v of an endpoint with at least two leaf neighbors and at most one non-leaf neighbor. Then re-verify the three cases of Theorem 4 with this lemma stated explicitly. Additionally, rerun subcase c3 replacing the apparent typo by t(lca_N(x,z)) = t(v) and confirm that the pendant conclusion follows.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing flaw found. The reader's candidate weakest point — the assertion in the proof of Theorem 4 that the reduced tree contains a vertex adjacent to at least two leaves and at most one non-leaf — is correct. Since suppressing degree-2 vertices in an arboreal network removes only outdegree-2 roots, the reduced tree has no degree-2 vertices. For any finite tree with no degree-2 vertices and at least five leaves, take a longest leaf-to-leaf path and let v be the neighbor of one endpoint. If v had a non-leaf neighbor off the path, that neighbor would lead to a leaf and yield a longer path; hence v has at most one non-leaf neighbor. Degree at least 3 then forces at least two leaf neighbors. With this lemma stated explicitly, the case analysis (a)-(c) of Theorem 4 is valid: each case produces a false-twin, true-twin, or pendant extension from a smaller arboreal-explainable graph, exactly as written. The only blemish is a typo in subcase c3: 't(lca_N(y,z)) = t(v)' should read 't(lca_N(x,z)) = t(v)'; the intended conclusion that x is pendant to y follows immediately. This is not a substantive gap.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces arboreal networks, a generalization of rooted phylogenetic trees in which several roots are allowed, and studies undirected graphs that can be represented by such networks with a {0,1}-labelling of the branching vertices. The main result, Theorem 4, states that a graph is arboreal-explainable if and only if it is distance-hereditary. The forward direction is proved constructively by Algorithm 1, which converts a sequence of one-vertex extensions of a distance-hereditary graph into a labelled arboreal network. The converse is proved by induction on the number of leaves, using a reduction of the underlying tree and a case analysis on a suitably chosen vertex. The paper also contains a characterization of pairs (G,G*) consisting of a graph and a Ptolemaic supergraph realizable by the same arboreal network (Theorem 6), and a characterization of graphs explainable by a two-rooted arboreal network (Theorem 7).","tokens_in":34525,"tokens_out":18795,"duration_ms":196388,"significance":"If the main theorem is taken together with the standard cograph/rooted-tree correspondence, it gives a clean analogue for distance-hereditary graphs: the class of graphs explainable by labelled arboreal networks is exactly a well-studied hereditary graph class. The proof is constructive in one direction and the algorithm uses the known linear-time construction of one-vertex extension sequences. The additional theorems on Ptolemaic supergraphs and two-rooted networks are nontrivial and make the paper more than a single equivalence. The result is likely to be of interest to researchers working on graph representations and phylogenetic networks.","major_comments":[{"comment":"As stated, the main equivalence is false for the single-vertex graph. Under the definition of a network in Section 3, every indegree-0 vertex must have outdegree at least 2 and every leaf must have indegree 1, so no arboreal network can have exactly one leaf. The single-vertex graph is distance-hereditary but not arboreal-explainable, and Algorithm 1 explicitly assumes |X| >= 2. Please either add an explicit degenerate-case exception (for example, allowing a one-vertex network, or treating the single-vertex graph vacuously) or state Theorem 4 and related results for graphs with at least two vertices.","section":"Section 3 and Theorem 4"},{"comment":"The induction in the converse direction relies on the assertion that after suppressing degree-2 vertices, the reduced tree N contains a vertex v that is adjacent to at least two leaves and to at most one non-leaf vertex. This fact is stated without proof or citation, and it is load-bearing because the subsequent case analysis (a)-(c) requires such a vertex. The statement is true and can be proved by taking a longest leaf-to-leaf path and examining the neighbour of an endpoint, but it should be stated and proved as a lemma before being used.","section":"Theorem 4, converse proof"},{"comment":"In the subcase t(v)=0, the proof reads \"t(lca_N(y,z)) = t(v) = 0\". This is incorrect as written, since lca_N(y,z)=r and t(r)=1. The argument needs the statement \"t(lca_N(x,z)) = t(v) = 0\", which together with t(lca_N(y,z))=1 justifies the conclusion that x is pendant to y. Please correct this typo, as the current wording makes the inference in that subcase invalid.","section":"Theorem 4, case (c3)"}],"minor_comments":[{"comment":"There are numerous typographical errors, including \"unidrected\" in Section 1, \"aboreal\" in the output line of Algorithm 1, \"charactarize\" in Section 1, and \"manucript\" in the Acknowledgements. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The text says \"if N is binary, V*(N) ∩ H(N) =/ 0\", but by the immediately preceding definition every vertex in V*(N) has indegree 0 or 1 and every vertex in H(N) has outdegree 1, so the intersection should be empty. Please replace this with the intended statement.","section":"Section 3, definition of binary network"},{"comment":"In the proof, the notation \"lca(y,z)\" is used instead of \"lca_N(y,z)\" in one place. This is cosmetic but should be made uniform for readability.","section":"Lemma 7(ii)"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Clean result, mostly airtight. The paper proves that distance-hereditary graphs are exactly the graphs explainable by labelled arboreal networks, and gives a construction (Algorithm 1) that turns a one-vertex-extension sequence into a binary arboreal network. That's a genuine new characterization, not just a reformulation: cographs as labelled rooted trees and Ptolemaic graphs as shared-ancestry graphs were known, but nobody had put distance-hereditary graphs in this particular spot.\n\nThe proof is careful. The forward direction is an induction on the extension sequence, with the network operations matching the three extension operations. The converse is a leaf-peeling induction on the reduced underlying tree. The one soft spot is an unproved tree fact in the converse: the claim that the reduced tree has a vertex adjacent to at least two leaves and at most one non-leaf. It's stated without proof, and it's load-bearing for the case analysis. The stress-test note is right that it's true—a longest path argument does it—but it should be stated as a lemma and proved. There's also a typo in subcase c3: 't(lca_N(y,z))' should be 't(lca_N(x,z))'. Both are minor editorial issues, not mathematical gaps.\n\nSections 6 and 7 extend the story: Section 6 characterizes which Ptolemaic supergraphs are realizable, using the symbolic-map machinery from [27]; Section 7 gives a forbidden-subgraph characterization for two-root networks via GATEX graphs. These are secondary but useful, and they tie the result into the existing literature cleanly. The paper relies heavily on [27] for symbolic maps and for the Ptolemaic characterization; since [27] is published and the results are directly relevant, that's legitimate.\n\nNo data, no code, but the algorithm is specified in pseudocode and the proof is constructive. The writing is dense but clear. If I were refereeing, I'd ask for the tree lemma to be made explicit and for the typo fixed, and then I'd be happy to accept. Worth sending to a serious referee.","headline":"New characterization of distance-hereditary graphs as arboreal-explainable: solid, clean, with a minor unproved tree fact and a typo, easily fixed.","tokens_in":35078,"tokens_out":2290,"would_cite":true,"duration_ms":22391,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C05","05C20","05C62"],"pacs":[],"model":"deepseek-v4-flash","headline":"The undirected graphs explainable by a labelled multi-rooted tree are precisely the distance-hereditary graphs.","keywords":["arboreal networks","distance-hereditary graphs","multi-rooted trees","cographs","least common ancestor","graph representation","Ptolemaic graphs","GATEX graphs"],"falsifier":"Enumerate all trees with five or more leaves and no degree-2 vertices, and check whether every such tree contains a vertex adjacent to at least two leaves and at most one non-leaf vertex; exhibiting one without such a vertex would falsify the unproved structural step on which the converse of Theorem 4 rests. Alternatively, run Algorithm 1 on every distance-hereditary graph up to a given size and verify that the returned labelled arboreal network explains the input graph, and check that no non-distance-hereditary graph is explained by any small arboreal network.","tokens_in":34102,"feed_emoji":"🌳","tokens_out":6395,"duration_ms":52969,"temperature":0.7,"pith_summary":"The paper proves that the undirected graphs explainable by a labelled arboreal network — a tree-like directed graph with possibly several roots and 0/1 labels on its branching vertices — are exactly the distance-hereditary graphs. This generalizes the classical correspondence between cographs and labelled rooted trees, where the root is unique. The forward direction is constructive: given any distance-hereditary graph, Algorithm 1 builds a binary labelled arboreal network that explains it. The reverse direction shows that no other graph admits such an explanation. If correct, the result gives a single tree-like representation for an entire well-studied graph class.","feed_headline":"Multi-rooted trees explain exactly distance-hereditary graphs","feed_subtitle":"A labelled network with several roots reproduces and extends the classic cograph–tree correspondence.","key_machinery":"The central object is the labelled arboreal network (N,t): a directed acyclic graph whose underlying undirected graph is a tree, allowing multiple roots, where t labels every vertex of outdegree at least two by 0 or 1. The argument is carried by the unique least common ancestor lemma for arboreal networks: leaves sharing an ancestor have a well-defined lca, so adjacency in the explained graph is determined by the label of that lca. For the constructive direction, Algorithm 1 turns the standard recursive generation of distance-hereditary graphs by pendant-vertex, false-twin, and true-twin operations into network-building steps that subdivide incoming arcs.","core_discovery":"Theorem 4 establishes an exact characterization: an undirected graph G is arboreal-explainable if and only if G is distance-hereditary. Here an arboreal network is a connected directed acyclic graph whose underlying undirected graph is a tree, with no vertex of both indegree and outdegree one, and a labelling assigns each branching vertex a 0 or 1; the network explains G when two distinct leaves are adjacent exactly when they share an ancestor and the label of their unique least common ancestor is 1. The paper further shows that every distance-hereditary graph with at least two vertices can be built, from any sequence of one-vertex extensions, into a binary labelled arboreal network (Algorithm 1), and it characterizes which graphs need exactly two roots (Theorem 7).","pith_inferences":["Because cograph algorithms often run on the labelled tree rather than on the graph itself, the same two-layer approach may now be tried on distance-hereditary graphs using arboreal networks, potentially turning NP-hard problems into polynomial ones for a much larger class.","The unproved tree lemma in the converse is standard and likely true; making it explicit would make the induction fully self-contained.","In evolutionary orthology inference, where a graph of paralog/ortholog relations may fail to be a cograph, multi-rooted networks offer a representation that relaxes the single-root assumption while staying within a tree-like structure.","The Ptolemaic supergraph characterization of Section 6 could serve as a tool for studying minimum chordal completions of distance-hereditary graphs, connecting to the open question the paper states."],"forward_implications":["Every distance-hereditary graph admits a binary labelled arboreal network of the same leaf set, so the tree-like representation is available for the whole class, not just cographs.","The one-root case recovers exactly the cographs; the constant-label-1 case recovers the connected Ptolemaic graphs, so distance-hereditary graphs interpolate between these two classical families.","Algorithm 1 constructs the network from any sequence of one-vertex extensions in time proportional to finding that sequence, giving an explicit representation for every distance-hereditary graph.","Corollary 1 restates the characterization in forbidden-subgraph form: arboreal-explainable graphs are exactly the hole-free graphs with no induced house, gem, or domino.","Theorem 7 pins down the two-root case: a non-cograph is explainable with exactly two roots precisely when it is a distance-hereditary GATEX graph with exactly one non-cograph connected component."],"supporting_citations":[{"why":"Defines arboreal networks, proves the unique least common ancestor lemma, and characterizes shared ancestry graphs as Ptolemaic — the foundation on which the paper defines arboreal-explainable graphs.","marker":"[27]"},{"why":"Introduces distance-hereditary graphs, the class the paper characterizes.","marker":"[24]"},{"why":"Gives the pendant-vertex / false-twin / true-twin recursive construction that Algorithm 1 turns into a labelled arboreal network.","marker":"[2]"},{"why":"Supplies the forbidden-induced-subgraph characterization of distance-hereditary graphs and the linear-time one-vertex-extension sequence used by Algorithm 1.","marker":"[15]"},{"why":"Establishes the cograph–labelled rooted tree correspondence that the paper's main theorem generalizes.","marker":"[5]"},{"why":"Introduces laminar trees for Ptolemaic graphs, the nearby structure behind the Ptolemaic supergraph results in Section 6.","marker":"[37]"}],"fun_headline_variants":["Arboreal networks exactly match distance-hereditary graphs","Distance-hereditary graphs are precisely multi-rooted tree explainable","Multi-rooted tree networks capture distance-hereditary graphs exactly","Exact characterization: distance-hereditary = arboreal-explainable","Tree generalization reveals distance-hereditary graph identity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The converse of Theorem 4 relies on an unproved structural fact: after suppressing degree-2 vertices, the underlying tree of an arboreal network with at least five leaves has some vertex adjacent to at least two leaves and to at most one non-leaf vertex; if this fact failed, the induction removing leaves one at a time would break.","fun_headline_variants_meta":{"raw":{"variants":["Arboreal networks exactly match distance-hereditary graphs","Distance-hereditary graphs are precisely multi-rooted tree explainable","Multi-rooted tree networks capture distance-hereditary graphs exactly","Exact characterization: distance-hereditary = arboreal-explainable","Tree generalization reveals distance-hereditary graph identity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00015,"raw_usage":{"total_tokens":1103,"prompt_tokens":755,"completion_tokens":348,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":371,"completion_tokens_details":{"reasoning_tokens":263}},"tokens_in":371,"tokens_out":348,"duration_ms":3691,"temperature":1.0,"reasoning_tokens":263,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-08T05:50:13.934315+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all trees with five or more leaves and no degree-2 vertices, and check whether every such tree contains a vertex adjacent to at least two leaves and at most one non-leaf vertex; exhibiting one without such a vertex would falsify the unproved structural step on which the converse of Theorem 4 rests. Alternatively, run Algorithm 1 on every distance-hereditary graph up to a given size and verify that the returned labelled arboreal network explains the input graph, and check that no non-distance-hereditary graph is explained by any small arboreal network.","supporting_citations":[{"cited_title":"SIAM journal on Discrete Mathe- matics 38(4), 2553–2577 (2024)","cited_arxiv_id":null,"evidence_quote":"Defines arboreal networks, proves the unique least common ancestor lemma, and characterizes shared ancestry graphs as Ptolemaic — the foundation on which the paper defines arboreal-explainable graphs."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Introduces distance-hereditary graphs, the class the paper characterizes."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the pendant-vertex / false-twin / true-twin recursive construction that Algorithm 1 turns into a labelled arboreal network."},{"cited_title":"Discrete Applied Mathematics 27(1), 85–99 (1990)","cited_arxiv_id":null,"evidence_quote":"Supplies the forbidden-induced-subgraph characterization of distance-hereditary graphs and the linear-time one-vertex-extension sequence used by Algorithm 1."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the cograph–labelled rooted tree correspondence that the paper's main theorem generalizes."},{"cited_title":"Discrete Applied Mathematics157(7), 1533–1543 (2009)","cited_arxiv_id":null,"evidence_quote":"Introduces laminar trees for Ptolemaic graphs, the nearby structure behind the Ptolemaic supergraph results in Section 6."}],"review_version":1}