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.

21 pages, 4 figures