Global Least Common Ancestor (LCA) Networks
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.
Authors
- Anna Lindeberg (ORCID: https://orcid.org/0000-0001-9664-1918)
- Peter Florian Stadler (ORCID: https://orcid.org/0000-0002-5016-5191)
- Marc Hellmuth (ORCID: https://orcid.org/0000-0002-1620-5508)
- Ameera Vaheeda Shanavas (ORCID: https://orcid.org/0000-0003-0038-5492)
- Manoj Changat (ORCID: https://orcid.org/0000-0001-7257-6031)
- Bruno J. Schmidt (ORCID: https://orcid.org/0000-0002-8808-5410)
Institutions
- University of Kerala (IN)
- Stockholm University (SE)
- Telstra (Australia) (AU)
- Max Planck Institute for Mathematics in the Sciences (DE)
- Leipzig University (DE)
Publication Details
- Journal
- Annals of Combinatorics
- Published
- 2026-11-16
- DOI
- https://doi.org/10.1007/s00026-026-00861-7
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Department of Science and Technology, Ministry of Science and Technology, India
- Deutscher Akademischer Austauschdienst
- Bundesministerium für Bildung und Forschung
- Sächsisches Staatsministerium für Wissenschaft und Kunst
- Indo-German Science and Technology Centre
- Human Resource Development Group
- German Academic Exchange Service New Delhi