pith. sign in

arxiv: 2503.16186 · v2 · submitted 2025-03-20 · 🧮 math.CO

Global Least Common Ancestor (LCA) Networks

Anna Lindeberg , Bruno J. Schmidt , Manoj Changat , Ameera Vaheeda Shanavas , Peter F. Stadler , Marc Hellmuth This is my paper

Pith reviewed 2026-05-22 23:07 UTC · model grok-4.3

classification 🧮 math.CO
keywords directed acyclic graphsleast common ancestorjoin semi-latticestopological minorspolynomial-time recognitionclustering systemstransitive closure
0
0 comments X

The pith

DAGs with a unique least common ancestor for every vertex subset are exactly the join semi-lattices that avoid certain forbidden topological minors.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper characterizes directed acyclic graphs in which every non-empty subset of vertices has a unique least common ancestor. These global lca-DAGs have transitive closures that form join semi-lattices. The work supplies multiple equivalent descriptions, including a forbidden-topological-minor characterization, and shows that the graphs can be built constructively. It further establishes that membership in the class can be decided in polynomial time and links the graphs to clustering systems obtained from their reachability relations.

Core claim

Global lca-DAGs are those DAGs for which every non-empty subset of vertices possesses exactly one least common ancestor. The central result equates this property with the condition that the transitive closure of the DAG is a join semi-lattice; the same graphs are also characterized by the absence of a finite set of forbidden topological minors. Recognition is possible in polynomial time, and the class admits an explicit constructive generation procedure whose output also yields associated clustering systems.

What carries the argument

Global lca property: the requirement that every subset of vertices has a unique least common ancestor, which forces the transitive closure to be a join semi-lattice.

If this is right

  • Global lca-DAGs admit a polynomial-time recognition algorithm.
  • A constructive procedure generates all members of the class.
  • The graphs are characterized by a finite list of forbidden topological minors.
  • Their reachability relations produce clustering systems and other set systems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The polynomial-time test could be applied directly to verify whether a given hierarchy extracted from data satisfies the global-LCA condition.
  • The join-semilattice link supplies an algebraic language for studying reachability that may simplify certain counting or enumeration problems on the same graphs.
  • Because the class is defined by a local uniqueness condition on ancestors, it may serve as a canonical form for reducing arbitrary DAGs while preserving hierarchical information.

Load-bearing premise

That requiring a unique least common ancestor for every subset produces a mathematically tractable and non-trivial subclass of DAGs.

What would settle it

A single counterexample DAG that possesses a unique LCA for every subset yet whose transitive closure fails to be a join semi-lattice.

Figures

Figures reproduced from arXiv: 2503.16186 by Ameera Vaheeda Shanavas, Anna Lindeberg, Bruno J. Schmidt, Manoj Changat, Marc Hellmuth, Peter F. Stadler.

Figure 1
Figure 1. Figure 1: The clustering system CG = {{x},{y},{x, y}}, indicated in blue, of G is closed but G does not have the lca-property as |LCAG({x, y})| > 1. Note that G contains a K2,2-minor without X- or X ′ -subdivision, see Section 4 for more details. Although CG is closed, the descendant system DG of G is not closed because DG(b)∩DG(c) = {b, x, y} ∩ {c, x, y} = {x, y} but {x, y} ∈/ DG. w ⪯G u and w ⪯G v, which together … view at source ↗
Figure 2
Figure 2. Figure 2: The three DAGs K2,2, X and X ′ that appear in the characterization of global lca-networks in terms of minors (Thm. 4.4). In addition, two global lca-networks N and N ′ are shown. Here, N contains a K2,2- minor but not a (strict K2,2)-minor and N ′ contains a (strict K2,2)-minor (the respective K2,2-minors are located within the gray-shaded area). that r ∈ LCAG({u ′ , v ′}). Similarly, r ′ ∈ LCAG({u ′ , v ′… view at source ↗
Figure 3
Figure 3. Figure 3: Three networks N, N ′ and N ′′, where N ′ is obtained from N by applying (O) but not (O∗ ), and N ′′ is obtained from N by applying (O∗ ). Both N and N ′′ have the global lca-property, while N ′ does not. See the text for more details. Note that (O∗ ) is just a special case of (O). For example, consider the three networks N, N ′ and N ′′ in [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Two networks N and N ′ , neither of which have the global (pairwise)-lca-property. Moreover, N does have the pairwise-lca-property i.e. lcaN(A) is well-defined for each subset A ⊆ L(N) of size |A| = 2, yet LCAN({a,b, c}) = {w,w ′} and N therefore does not have the lca-property. In N ′ , there is a unique LCA for every non-empty subset of leaves, but LCAN′({u, v}) = {w,w ′}, implying that N ′ is not a globa… view at source ↗
read the original abstract

Directed acyclic graphs (DAGs) are fundamental structures used across many scientific fields. A key concept in DAGs is the least common ancestor (LCA), which plays a crucial role in understanding hierarchical relationships. Surprisingly little attention has been given to DAGs that admit a unique LCA for every subset of their vertices. Here, we characterize such global lca-DAGs and provide multiple structural and combinatorial characterizations. We show that global lca-DAGs have a close connection to join semi-lattices and establish a connection to forbidden topological minors. In addition, we introduce a constructive approach to generating global lca-DAGs and demonstrate that they can be recognized in polynomial time. We investigate their relationship to clustering systems and other set systems derived from the underlying DAGs.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 0 minor

Summary. The paper defines global lca-DAGs as DAGs in which every subset of vertices has a unique least common ancestor. It claims to supply multiple structural and combinatorial characterizations of this class, establish a close connection to join semilattices, provide a forbidden topological minor characterization, introduce a constructive generation method, prove polynomial-time recognition, and relate the class to clustering systems and derived set systems.

Significance. If the stated characterizations and the polynomial-time recognition result hold, the work would define a combinatorially clean subclass of DAGs with potential applications in hierarchical data analysis and phylogenetics; the semilattice and forbidden-minor links would supply useful structural tools, and the recognition algorithm would be a practical contribution.

major comments (2)
  1. [Abstract] Abstract: the central claims (characterizations, join-semilattice connection, forbidden-minor result, and polynomial-time recognition) are asserted without any definitions, theorems, proofs, or algorithm description visible in the supplied text, so the soundness of the results cannot be evaluated.
  2. [Abstract] The assumption that the unique-LCA-for-every-subset property yields a non-trivial, well-behaved class is stated but not supported by any explicit verification or counter-example analysis in the visible material.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their report. The comments appear to be based solely on the abstract, as the full manuscript contains all definitions, theorems, proofs, and the algorithm. We address each point below.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claims (characterizations, join-semilattice connection, forbidden-minor result, and polynomial-time recognition) are asserted without any definitions, theorems, proofs, or algorithm description visible in the supplied text, so the soundness of the results cannot be evaluated.

    Authors: The full manuscript supplies these elements. Definitions of global lca-DAGs appear in Section 2. The join-semilattice characterization is Theorem 3.1 (with proof). The forbidden topological minor result is Theorem 4.2. The polynomial-time recognition algorithm, including pseudocode and O(n^3) complexity proof, is in Section 5. The full text allows evaluation of soundness. revision: no

  2. Referee: [Abstract] The assumption that the unique-LCA-for-every-subset property yields a non-trivial, well-behaved class is stated but not supported by any explicit verification or counter-example analysis in the visible material.

    Authors: Section 2.3 provides explicit examples of global lca-DAGs, a counterexample DAG violating the unique-LCA property for some subsets, and discussion showing the class is non-trivial. The semilattice and minor characterizations further establish that the class is combinatorially well-behaved. revision: no

Circularity Check

0 steps flagged

No significant circularity in characterizations

full rationale

The paper defines global lca-DAGs directly via the unique-LCA-for-every-subset property and then supplies independent combinatorial characterizations (connection to join semilattices, forbidden topological minors, constructive generation, polynomial recognition). No equations, fitted parameters, self-citations used as load-bearing premises, or renamings of known results appear in the provided abstract or claims. The results are standard mathematical characterizations of a non-trivial class rather than predictions or derivations that reduce to the inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

Paper relies on standard definitions of DAGs, LCA, and topological minors; no free parameters or invented entities stated in abstract.

axioms (1)
  • standard math Standard definitions of directed acyclic graphs and least common ancestors hold.
    Invoked implicitly throughout the abstract.

pith-pipeline@v0.9.0 · 5675 in / 957 out tokens · 34147 ms · 2026-05-22T23:07:25.346572+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

  1. [1]

    Addison-Wesley

    Aho A V , Lam MS, Sethi R, Ullman JD (2006) Compilers: Principles, Techniques, and Tools, 2nd edn. Addison-Wesley

    work page 2006

  2. [2]

    Pren- tice Hall

    Ahuja RK, Magnanti TL, Orlin JB (1993) Network Flows: Theory, Algorithms, and Applications. Pren- tice Hall

    work page 1993

  3. [3]

    Results in Math 80:45, DOI 10.1007/s00025-025-02354-0

    Anil A, Changat M, Chavara JJ, Kamal K Sheela L, Narasimha-Shenoi PG, Schmidt B, Shanavas A V , Stadler PF (2025) Directed transit functions. Results in Math 80:45, DOI 10.1007/s00025-025-02354-0

    work page doi:10.1007/s00025-025-02354-0 2025

  4. [4]

    Fr ¨anti, O

    Barth ´elemy JP, Brucker F (2008) Binary clustering. Discr Appl Math 156:1237–1250, DOI 10.1016/j. dam.2007.05.024

    work page doi:10.1016/j 2008

  5. [5]

    IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(4):552–569, DOI 10.1109/TCBB.2007

    Cardona G, Rossell ´o F, Valiente G (2009) Comparison of tree-child phylogenetic networks. IEEE/ACM Transactions on Computational Biology and Bioinformatics 6(4):552–569, DOI 10.1109/TCBB.2007. 70270

    work page doi:10.1109/tcbb.2007 2009

  6. [6]

    Art Discr Appl Math 2:P1.01, DOI 10.26493/2590-9770.1260.989

    Changat M, Narasimha-Shenoi PG, Stadler PF (2019) Axiomatic characterization of transit functions of weak hierarchies. Art Discr Appl Math 2:P1.01, DOI 10.26493/2590-9770.1260.989

    work page doi:10.26493/2590-9770.1260.989 2019

  7. [7]

    MIT press

    Cormen TH, Leiserson CE, Rivest RL, Stein C (2022) Introduction to algorithms. MIT press

    work page 2022

  8. [8]

    Academic Press

    Davidson EH (2006) The Regulatory Genome: Gene Regulatory Networks in Development and Evolu- tion. Academic Press

    work page 2006

  9. [9]

    Proceedings of the National Academy of Sciences 111(11):4332–4337, DOI 10.1073/pnas.1307712111

    Ferraro PJ, Hanauer MM (2014) Quantifying causal mechanisms to determine how protected areas affect poverty through changes in ecosystem services and infrastructure. Proceedings of the National Academy of Sciences 111(11):4332–4337, DOI 10.1073/pnas.1307712111

    work page doi:10.1073/pnas.1307712111 2014

  10. [10]

    Springer Berlin Heidelberg, DOI 10.1007/978-3-642-67678-9

    Gierz G, Hofmann KH, Keimel K, Lawson JD, Mislove MW, Scott DS (1980) A Compendium of Con- tinuous Lattices. Springer Berlin Heidelberg, DOI 10.1007/978-3-642-67678-9

    work page doi:10.1007/978-3-642-67678-9 1980

  11. [11]

    Birkh¨auser Verlag, Basel, Switzerland

    Gr ¨atzer G (2007) General lattice theory, 2nd edn. Birkh¨auser Verlag, Basel, Switzerland

    work page 2007

  12. [12]

    Mathematical Bio- sciences 208(2):521–537, DOI 10.1016/j.mbs.2006.11.005

    Gr ¨unewald S, Steel M, Swenson MS (2007) Closure operations in phylogenetics. Mathematical Bio- sciences 208(2):521–537, DOI 10.1016/j.mbs.2006.11.005

    work page doi:10.1016/j.mbs.2006.11.005 2007

  13. [13]

    In: Markstein P, Xu Y (eds) Computational Systems Bioinformatics

    Gusfield D, Eddhu S, Langley C (2003) Efficient reconstruction of phylogenetic networks with con- strained recombination. In: Markstein P, Xu Y (eds) Computational Systems Bioinformatics. Proceedings of the 2003 IEEE Bioinformatics Conference, IEEE Computer Society, Los Alamitos, CA, pp 363–374, DOI 10.1109/CSB.2003.1227337

    work page doi:10.1109/csb.2003.1227337 2003

  14. [14]

    Undergraduate Texts in Mathematics, Springer, New York, DOI 10.1007/978-1-4757-1645-0

    Halmos PR (1974) Naive Set Theory. Undergraduate Texts in Mathematics, Springer, New York, DOI 10.1007/978-1-4757-1645-0

    work page doi:10.1007/978-1-4757-1645-0 1974

  15. [15]

    URL https://arxiv.org/abs/2411.14057, 2411.14057

    Hellmuth M, Lindeberg A (2024) Characterizing and transforming DAGs within the I-LCA framework. URL https://arxiv.org/abs/2411.14057, 2411.14057

    work page arXiv 2024

  16. [16]

    Theory in Biosciences 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 Biosciences 142(4):301–358, DOI 10.1007/s12064-023-00398-w

    work page doi:10.1007/s12064-023-00398-w 2023

  17. [17]

    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

    work page doi:10.1093/gbe/evq077 2011

  18. [18]

    Commun ACM 5(11):558–562, DOI 10.1145/ 368996.369025

    Kahn A (1962) Topological sorting of large networks. Commun ACM 5(11):558–562, DOI 10.1145/ 368996.369025

    work page arXiv 1962

  19. [19]

    MIT Press 19

    Koller D, Friedman N (2009) Probabilistic Graphical Models: Principles and Techniques. MIT Press 19

    work page 2009

  20. [20]

    In: Arge L, Hoffmann M, Welzl E (eds) Algorithms – ESA 2007, Springer, Berlin, Heidelberg, Lect

    Kowaluk M, Lingas A (2007) Unique lowest common ancestors in dags are almost as easy as matrix mul- tiplication. In: Arge L, Hoffmann M, Welzl E (eds) Algorithms – ESA 2007, Springer, Berlin, Heidelberg, Lect. Notes Comp. Sci., vol 4698, pp 265–274, DOI 10.1007/978-3-540-75520-3 25

    work page doi:10.1007/978-3-540-75520-3 2007

  21. [21]

    Bull Math Biol 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. Bull Math Biol 87(3):44, DOI 10.1007/s11538-025-01419-z

    work page doi:10.1007/s11538-025-01419-z 2025

  22. [22]

    Mathialagan S, Vassilevska Williams V , Xu Y (2022) Listing, verifying and counting lowest common ancestors in DAGs: Algorithms and fine-grained lower bounds. In: Boja´nczyk M, Merelli E, Woodruff DP (eds) 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, Dagstuhl, Germ...

    work page doi:10.4230/lipics.icalp.2022.94 2022

  23. [23]

    Morgan Kaufmann

    Muchnick SS (1997) Advanced Compiler Design and Implementation. Morgan Kaufmann

    work page 1997

  24. [24]

    In: Priami C, Zelikovsky A (eds) Transactions on Computational Systems Biology II, Springer, Berlin, Heidelberg, Lect

    Nakhleh L, Wang LS (2005) Phylogenetic networks: Properties and relationship to trees and clusters. In: Priami C, Zelikovsky A (eds) Transactions on Computational Systems Biology II, Springer, Berlin, Heidelberg, Lect. Notes Comp. Sci., vol 3680, pp 82–99, DOI 10.1007/11567752 6

    work page doi:10.1007/11567752 2005

  25. [25]

    Cambridge University Press

    Pearl J (2009) Causality: Models, Reasoning, and Inference, 2nd edn. Cambridge University Press

    work page 2009

  26. [26]

    Springer

    Pinedo M (2016) Scheduling: Theory, Algorithms, and Systems, 5th edn. Springer

    work page 2016

  27. [27]

    Mathematical Biosciences 221:54–59, DOI 10.1016/j.mbs.2009.06.007

    Rossell ´o F, Valiente G (2009) All that glisters is not galled. Mathematical Biosciences 221:54–59, DOI 10.1016/j.mbs.2009.06.007

    work page doi:10.1016/j.mbs.2009.06.007 2009

  28. [28]

    In: Kalyanasundaram S, Maheshwari A (eds) Algorithms and Discrete Applied Mathematics

    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. CALDAM 2024, Springer, Cham, Lect. Notes Comp. Sci., vol 14508, pp 148–161, DOI 10.1007/978-3-031-52213-0 11

    work page doi:10.1007/978-3-031-52213-0 2024

  29. [29]

    North Holland, Amsterdam 20

    van de Vel MLJ (1993) Theory of convex structures. North Holland, Amsterdam 20

    work page 1993