REVIEW 2 major objections 7 minor 1 cited by
Characterizing and Transforming DAGs within the I-LCA Framework
T0 review · 2 major / 7 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper characterizes exactly which clusters survive the I1-LCA simplification of a DAG: those that are inclusion-minimal containers of some allowed leaf set, with a unique choice of removed vertices.
desk verdict The main theorem is real and the proofs look sound, but the abstract and Section 5 overstate Theorem 4.5 by dropping the k > 1 hypothesis. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery is the pair consisting of the cluster subsystem $\mathcal{C}_G(I_1)$ and the $\ominus$-operator. For a set system $\mathcal{C}$, the subsystem $\mathcal{C}(I_1)$ collects exactly the clusters that satisfy property (I1-C): each is the unique inclusion-minimal element of $\mathcal{C}$ containing some subset $A$ of leaves with $|A|\in I_1$. The $\ominus$-operator deletes a vertex and joins each parent to each child; earlier work guarantees properties (S0)--(S4), which say the deletion introduces no new clusters, keeps the same leaves, keeps the same vertex set minus the deleted vertices, preserves the ancestor order, and preserves well-defined LCAs of allowed leaf sets. These properties let the proof show that the clusters of the simplified graph are exactly $\mathcal{C}_G(I_1)$, and that this subsystem is $I_1$-ary.
What would settle it
Build a small DAG with the $\{1,2\}$-lca-property, list the vertices that are not the unique LCA of any two leaves, delete all of them with $\ominus$, then remove shortcut edges. If the resulting cluster system differs from the set of clusters that are inclusion-minimal containers of some two leaves, or if the shortcut-free graph is not isomorphic to the Hasse diagram of that cluster set, Theorem 3.9 is false. A brute-force enumeration of all DAGs on four leaves would settle this completely.
Extended reading notes
Core claim
The central result is Theorem 3.9. Let $G$ be a DAG with the $I_1$-lca-property on leaf set $X$, and let $W$ be the set of all vertices that are not $I_1$-lca vertices. Then the shortcut-free graph $(G \ominus W)^-$ is isomorphic to the Hasse diagram $H(\mathcal{C}_G(I_1))$, where $\mathcal{C}_G(I_1)$ consists of those clusters in $\mathcal{C}_G$ that are the unique inclusion-minimal cluster containing some leaf set of size in $I_1$. In particular, $\mathcal{C}_{G\ominus W}=\mathcal{C}_{(G\ominus W)^-}=\mathcal{C}_G(I_1)$ is an $I_1$-ary set system, and $W$ is the unique, hence smallest, subset of vertices whose deletion makes the graph $I_1$-lca-relevant while preserving the structural properties (S0)--(S4).
Load-bearing premise
The load-bearing premise is that deleting vertices that are not unique LCAs of any allowed-size leaf set never changes the unique LCA of an allowed-size leaf set when that LCA already exists. If that preservation lemma from the earlier framework fails, the characterization of surviving clusters and the uniqueness of the deleted set both collapse.
Editorial extensions
If this is right
- For any DAG with the $I_1$-lca-property, the clusters lost under the simplification are exactly $\mathcal{C}_G \setminus \mathcal{C}_G(I_1)$, so the loss is determined by the cluster system alone, not by the particular choice of $W$.
- The vertex set $W$ whose deletion produces an $I_1$-lca-relevant DAG while preserving (S0)--(S4) is unique, hence the transformation is canonical for this class.
- If $\mathcal{C}_G$ is tree-like, then $(G \ominus W)^-$ is a phylogenetic tree with the same cluster system; if $\mathcal{C}_G$ is galled-tree-like, it is a galled-tree with the same clusters.
- The theorem extends earlier binary and $k$-ary set-system characterizations to arbitrary sets $I_1$ of allowed leaf-set sizes.
- Since $(G \ominus W)^-$ is always regular, the simplification ends in a canonical Hasse-diagram object determined by $\mathcal{C}_G(I_1)$.
Reading between the lines
- A computational search over small DAGs could test whether cluster survival for DAGs lacking the $I_1$-lca-property admits a similar description in terms of inclusion-minimal clusters or requires tracking the full LCA structure.
- For the orthology-motivated case $I_1=\{1,2\}$, the theorem identifies a canonical simplification that preserves exactly the pairwise-LCA information, which may serve as a normal form for orthology-aware network simplification.
- The paper leaves open how the $\ominus$-operator relates to normalization by visible vertices; the uniqueness of $W$ here suggests that for $I_1$-lca-property DAGs the two procedures may agree more often than in general.
- A testable algorithmic extension: compute $\mathcal{C}_G(I_1)$ and compare it with $\mathcal{C}_G$ to decide in polynomial time whether a given DAG with the $I_1$-lca-property loses any clusters under simplification.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies DAGs within the I1-lca framework, where I1 is a set of leaf-subset sizes containing 1. It distinguishes between I1-lca-relevant DAGs and DAGs with the I1-lca-property, and relates these to pre-I1-ary and I1-ary set systems. The main results are: a characterization of the I1-lca-property for DAGs satisfying path-cluster-comparability (Theorem 3.5); characterizations of grounded pre-I1-ary and I1-ary set systems as cluster systems of such DAGs (Theorem 3.7); a characterization, for DAGs with the I1-lca-property, of the cluster system of the transformed DAG G ⊖ W as the set C_G(I1) of I1-minimal clusters, together with uniqueness of the removed vertex set W (Theorem 3.9); and a consequence for DAGs whose cluster system is tree-like or galled-tree-like, stating that (G ⊖ W)^− is a tree or galled-tree with the same cluster system (Theorem 4.5). The proofs are detailed and the paper generalizes earlier results for binary and k-ary set systems.
Significance. If the results hold, the paper provides a clean structural description of which clusters survive the ⊖-simplification for DAGs with the I1-lca-property, and it establishes uniqueness of the simplification. This is a useful contribution to the theory of LCA-based DAG simplification and generalizes prior work on binary and k-ary clustering systems. The paper is careful with definitions, provides helpful examples (Figures 1–3), and proves its main theorems in a coherent manner. The main caveat is that the central Theorem 3.9 leans on property (S4) of Theorem 2.12 imported from the authors' companion paper [19]; the paper does not reprove (S4). In addition, the abstract and Section 5 overstate Theorem 4.5 by omitting the hypothesis 1 < k ≤ κ_G. These issues are correctable and do not undermine the body's main derivation, but they do affect how the results are presented.
major comments (2)
- [Abstract and Section 5] The abstract and the Summary and Outlook section state that for a DAG G with the I1-lca-property whose cluster system is tree-like or galled-tree-like, the shortcut-free transformed DAG is always a tree or galled-tree and that C_H = C_G. This omits the hypothesis in Theorem 4.5 that I1 contains an integer k with 1 < k ≤ κ_G, where κ_G is the size of the smallest non-singleton cluster. Without this hypothesis the statement is false: if I1 = {1}, then every DAG has the I1-lca-property, and for a non-trivial tree G the set W of all non-I1-lca vertices deletes all internal vertices, so (G ⊖ W)^− is an edgeless graph whose cluster system is not C_G. The abstract and Section 5 should either include the condition 1 < k ≤ κ_G or restrict the claimed consequence to the cases actually covered by Theorem 4.5.
- [Theorem 3.9 and Lemma 3.3] The proof of Theorem 3.9 depends essentially on property (S4) of the imported Theorem 2.12 from [19], which asserts that lca_{G⊖W}(A) = lca_G(A) for every A ∈ X(I1) for which lca_G(A) is well-defined. This property is used in Lemma 3.3 to show that G ⊖ W retains the I1-lca-property, and it is used in the uniqueness argument of Theorem 3.9 to conclude that V(H) = V(H*) from the equality of lca values. The paper does not prove (S4) or justify it beyond citing [19]. Since the equality C_{G⊖W} = C_G(I1) and the uniqueness of W both rest on this imported property, the authors should either include a proof of (S4) or state explicitly that the main results are contingent on [19, Thm. 2.12] and give a precise location of its proof.
minor comments (7)
- [Abstract and Introduction] The abstract uses the symbol I, while the paper consistently uses I1 with the convention 1 ∈ I1. Please align the notation in the abstract with the body.
- [Introduction, paragraph 2] The phrase "cannot not serve as LCAs" should read "cannot serve as LCAs"; the double negative is confusing.
- [Section 2, Lemma 2.2] There is a typo: "Then. G′ := (V,E \ {e}) is a DAG" should have a colon or comma after "Then".
- [Section 3, Lemma 3.2] The condition "for some |I1| > 1" is awkward because I1 is a set; it would be clearer to write "for some set I1 containing an integer k > 1".
- [Section 4, Theorem 4.5] There is a typo in the statement: "with with 1 < k ≤ κG" should be "with 1 < k ≤ κG".
- [Figure 2 caption] The word "examplify" should be "exemplify".
- [Section 3, Theorem 3.9] The sentence "G⊖W and (G⊖W)− are I1-lca-REL DAGs on X with the I1-lca-property that satisfies (S0)–(S4)" has a subject-verb agreement error; it should read "that satisfy (S0)–(S4)".
Circularity Check
No significant circularity: Theorem 3.9 and the uniqueness of W are new consequences of prior published results, not restatements of the paper's assumptions.
full rationale
The paper's central claim (Theorem 3.9) is not equivalent to its inputs. The equality C_{G⊖W}=C_G(I1) is proved directly: each cluster in C_G(I1) is witnessed by an I1-lca vertex v=lca_G(A), and since v∉W and (S0) gives C_G(v)=C_{G⊖W}(v), the cluster survives; conversely, any surviving cluster comes from v∉W, which is an I1-lca vertex, so it satisfies (I1-C). This is a mathematical argument, not a definitional identity. The uniqueness of W is also derived: (S4) forces lca_G(A)=lca_H(A)=lca_{H*}(A) for all A∈X(I1), and since H and H* are I1-lca-REL, their vertex sets both equal {lca_G(A): A∈X(I1)}, giving W=W*. This deduction uses the imported property (S4) from [19, Thm. 2.12], but that prior theorem has stated assumptions that do not include the target result and is a published, independently checkable statement. Per the review rules, a parameter-free cited result with assumptions not containing the conclusion is real evidence and does not create circularity. The same applies to Proposition 2.10 ([19, Cor. 4.9]) on regularity: it is used to identify (G⊖W)- with H(C_G(I1)), but only after the cluster-set equality has been established. No fitted parameters are renamed as predictions, no ansatz is smuggled in via citation, and no known result is merely renamed. The paper is not fully self-contained because it relies on [19] and [21], but reliance on prior work is not circularity unless the argument reduces to an unverified self-citation; here it does not.
Assumptions & free parameters
assumptions (7)
- standard math All sets are finite, Section 2 first sentence.
- domain assumption Theorem 2.12 of [19]: for any subset W of non-I1-lca vertices, G ⊖ W is a DAG on X satisfying (S0) to (S4), and if W contains all non-I1-lca vertices then G ⊖ W is I1-lca-REL.
- domain assumption Proposition 2.10 of [19]: every I1-lca-REL DAG G has regular shortcut-free form G-.
- domain assumption Lemma 2.2 of [19]: deleting shortcuts preserves the ancestor partial order and all clusters.
- domain assumption Lemma 2.6 of [19]: H(C) is shortcut-free, satisfies PCC, and is regular and phylogenetic when C is grounded.
- domain assumption Lemma 4.2 and Corollary 4.3 of [19]: for every grounded set system C satisfying (N3O), there is a DAG with cluster system C in which every non-leaf is an ℓ-lca vertex for all 2 ≤ ℓ ≤ |C(v)|.
- domain assumption Theorem 4.1 from [13,20]: C is tree-like if and only if H(C) is a tree, and C is galled-tree-like if and only if H(C) is a galled-tree.
Cite this review
Pith. "Pith review of Characterizing and Transforming DAGs within the I-LCA Framework." pith.science (2026). https://pith.science/paper/TDQCJHRO
@misc{pith2026241114057,
author = {Pith},
title = {Pith review of: Characterizing and Transforming DAGs within the I-LCA Framework},
year = {2026},
howpublished = {\url{https://pith.science/paper/TDQCJHRO}},
note = {Machine review of arXiv:2411.14057}
}
abstract
We explore the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs), focusing on the interplay between so-called $I$-lca-relevant DAGs and DAGs with the $I$-lca-property. Here, $I$ denotes a set of integers. In $I$-lca-relevant DAGs, each vertex is the unique LCA for some subset $A$ of leaves of size $|A|\in I$, whereas in a DAG with the $I$-lca-property there exists a unique LCA for every subset $A$ of leaves satisfying $|A|\in I$. We elaborate on the difference between these two properties and establish their close relationship to pre-$I$-ary and $I$-ary set systems. This, in turn, generalizes results established for (pre-)binary and $k$-ary set systems. Moreover, we build upon recently established results that use a simple operator $\ominus$, enabling the transformation of arbitrary DAGs into $I$-lca-relevant DAGs. This process reduces unnecessary complexity while preserving key structural properties of the original DAG. The set $C_G$ consists of all clusters in a DAG $G$, where clusters correspond to the descendant leaves of vertices. While in some cases $C_H = C_G$ when transforming $G$ into an $I$-lca-relevant DAG $H$, it often happens that certain clusters in $C_G$ do not appear as clusters in $H$. To understand this phenomenon in detail, we characterize the subset of clusters in $C_G$ that remain in $H$ for DAGs $G$ with the $I$-lca-property. Furthermore, we show that the set $W$ of vertices required to transform $G$ into $H = G \ominus W$ is uniquely determined for such DAGs. This, in turn, allows us to show that the ``shortcut-free'' version of the transformed DAG $H$ is always a tree or a galled-tree whenever $C_G$ represents the clustering system of a tree or galled-tree and $G$ has the $I$-lca-property. In the latter case $C_H = C_G$ always holds.
Figures
Forward citations
Cited by 1 Pith paper
-
Orthology and Near-Cographs in the Context of Phylogenetic Networks
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.
Reference graph
Works this paper leans on
-
[19]
Bulletin of Mathematical Biology 87(3):44, DOI 10.1007/ s11538-025-01419-z
Lindeberg A, Hellmuth M (2025) Simplifying and characterizing DAGs and phylogenetic networks via least common ancestor constraints. Bulletin of Mathematical Biology 87(3):44, DOI 10.1007/ s11538-025-01419-z
work page 2025
-
[1]
Fundam Inf 134(1-2):1–15, DOI 10.3233/FI-2014-1087
Alcal `a A, Llabr´es M, Rossell´o F, Rullan P (2014) Tree-child cluster networks. Fundam Inf 134(1-2):1–15, DOI 10.3233/FI-2014-1087
-
[2]
Ann Comb 8:391– 408, DOI 10.1007/s00026-004-0228-0
Baroni M, Semple C, Steel M (2005) A framework for representing reticulate evolution. Ann Comb 8:391– 408, DOI 10.1007/s00026-004-0228-0
-
[3]
Discr Appl Math 156(8):1237–1250, DOI 10.1016/j.dam
Barth ´elemy JP, F (2008) Binary clustering. Discr Appl Math 156(8):1237–1250, DOI 10.1016/j.dam. 2007.05.024
doi:10.1016/j.dam 2008
-
[4]
Advances in Applied Mathematics 78:114– 141, DOI 10.1016/j.aam.2016.04.004
Bordewich M, Semple C (2016) Reticulation-visible networks. Advances in Applied Mathematics 78:114– 141, DOI 10.1016/j.aam.2016.04.004
-
[5]
Adv Data Anal Classif 3:189–204, DOI 10.1007/ s11634-009-0046-7
Brucker F, G ´ely A (2009) Parsimonious cluster systems. Adv Data Anal Classif 3:189–204, DOI 10.1007/ s11634-009-0046-7
work page 2009
-
[6]
Philosophical Transactions of the Royal Society B: Biological Sciences 364(1527):2187–2196, DOI 10
Dagan T, Martin W (2009) Getting a better picture of microbial evolution en route to a network of genomes. Philosophical Transactions of the Royal Society B: Biological Sciences 364(1527):2187–2196, DOI 10. 1098/rstb.2009.0040
-
[7]
Trends in Genetics 16(5):227–231, DOI 10.1016/S0168-9525(00)02005-9
Fitch WM (2000) Homology: a personal view on some of the problems. Trends in Genetics 16(5):227–231, DOI 10.1016/S0168-9525(00)02005-9
Show all 21 references
-
[8]
Molecular Phylogenetics and Evolution 163:107215, DOI 10.1016/j.ympev.2021.107215
Francis A, Huson DH, Steel M (2021) Normalising phylogenetic networks. Molecular Phylogenetics and Evolution 163:107215, DOI 10.1016/j.ympev.2021.107215
2021
-
[9]
J Math Biol 65:157–180, DOI 10.1007/s00285-011-0456-y
Gambette P, Huber KT (2012) On encodings of phylogenetic networks of bounded level. J Math Biol 65:157–180, DOI 10.1007/s00285-011-0456-y
2012 doi
-
[10]
In: Crandall KA, Lager- gren J (eds) Algorithms in Bioinformatics
H HD, Rupp R (2008) Summarizing multiple gene trees using cluster networks. In: Crandall KA, Lager- gren J (eds) Algorithms in Bioinformatics. W ABI, Lect. Notes Comp. Sci., vol 5251, Springer, Berlin, Heidelberg, DOI 10.1007/978-3-540-87361-7 25
2008 doi
-
[11]
Bulletin of Math- ematical Biology 87(2):20, DOI 10.1007/s11538-024-01398-7 10
Heiss J, Huson DH, Steel M (2025) Transformations to simplify phylogenetic networks. Bulletin of Math- ematical Biology 87(2):20, DOI 10.1007/s11538-024-01398-7 10
2025 doi
-
[12]
Journal of Mathematical Biology 66(1):399–420, DOI 10.1007/s00285-012-0525-x
Hellmuth M, Hernandez-Rosales M, Huber KT, Moulton V , Stadler PF, Wieseke N (2013) Orthology relations, symbolic ultrametrics, and cographs. Journal of Mathematical Biology 66(1):399–420, DOI 10.1007/s00285-012-0525-x
2013 doi
-
[13]
Theory in Bio- sciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w
Hellmuth M, Schaller D, Stadler PF (2023) Clustering systems of phylogenetic networks. Theory in Bio- sciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w
2023 doi
-
[14]
Journal of Theoretical Biology 404:30–39, DOI 10.1016/j.jtbi.2016.05.030
Huber KT, Moulton V , Wu T (2016) Transforming phylogenetic networks: Moving beyond tree space. Journal of Theoretical Biology 404:30–39, DOI 10.1016/j.jtbi.2016.05.030
2016 doi
-
[15]
Bull Math Biol 84(10):119, DOI 10
Huber KT, Moulton V , Scholz GE (2022) Forest-based networks. Bull Math Biol 84(10):119, DOI 10. 1007/s11538-022-01081-9
2022
-
[16]
Genome Biol Evol 3:23–35, DOI 10.1093/gbe/evq077
Huson DH, Scornavacca C (2011) A survey of combinatorial methods for phylogenetic networks. Genome Biol Evol 3:23–35, DOI 10.1093/gbe/evq077
2011 doi
-
[17]
Cambridge University Press, DOI 10.1017/CBO9780511974076
Huson DH, Rupp R, Scornavacca C (2011) Phylogenetic Networks: Concepts, Algorithms and Applica- tions. Cambridge University Press, DOI 10.1017/CBO9780511974076
2011 doi
-
[18]
Genome Biol 2(8):INTERAC- TIONS1002, DOI 10.1186/gb-2001-2-8-interactions1002
Jensen RA (2001) Orthologs and paralogs - we need to get it right. Genome Biol 2(8):INTERAC- TIONS1002, DOI 10.1186/gb-2001-2-8-interactions1002
2001 doi
-
[20]
Oxford University Press, Oxford, UK
Semple C, Steel M (2003) Phylogenetics, Oxford Lecture Series in Mathematics and its Applications, vol 24. Oxford University Press, Oxford, UK
2003
-
[21]
In: Kalyanasundaram S, Maheshwari A (eds) Algorithms and Discrete Applied Mathematics, Springer Nature Switzerland, Cham, pp 148–161, DOI 10.1007/978-3-031-52213-0 11 11
Shanavas A V , Changat M, Hellmuth M, Stadler PF (2024) Unique least common ancestors and clusters in directed acyclic graphs. In: Kalyanasundaram S, Maheshwari A (eds) Algorithms and Discrete Applied Mathematics, Springer Nature Switzerland, Cham, pp 148–161, DOI 10.1007/978-...
2024 doi
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.