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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
article

Global Least Common Ancestor (LCA) Networks

Anna Lindeberg, Peter Florian Stadler, Marc Hellmuth, Ameera Vaheeda Shanavas et al.
1 links
Annals of Combinatorics
Advanced Graph Theory Research
article

Global Least Common Ancestor (LCA) Networks

Anna Lindeberg, Peter Florian Stadler, Marc Hellmuth, Ameera Vaheeda Shanavas, Manoj Changat, Bruno J. Schmidt
article en

Abstract

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.

Annals of Combinatorics
University of Kerala (IN), Stockholm University (SE), Telstra (Australia) (AU), Max Planck Institute for Mathematics in the Sciences (DE), Leipzig University (DE)
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
Advanced Graph Theory Research
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon