Characterizing and transforming DAGs within the ℐ -lca framework
Marc Hellmuth, Anna Lindeberg · Discrete Applied Mathematics · 2025
We explore the connections between clusters and least common ancestors (LCAs) in directed acyclic graphs (DAGs), focusing on the interplay between so-called ℐ -lca-relevant DAGs and DAGs with the ℐ -lca-property. Here, ℐ denotes a set of integers. In ℐ -lca-relevant DAGs, each vertex is the unique LCA for some subset A of leaves of size | A | ∈ ℐ , whereas in a DAG with the ℐ -lca-property there exists a unique LCA for every subset A of leaves satisfying | A | ∈ ℐ . We elaborate on the difference between these two properties and establish their close relationship to pre- ℐ -ary and ℐ -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 ⊖ , enabling the transformation of arbitrary DAGs into ℐ -lca-relevant DAGs. This process reduces unnecessary complexity while preserving key structural properties of the original DAG. The set ℭ G consists of all clusters in a DAG G , where clusters correspond to the descendant leaves of vertices. While in some cases ℭ H = ℭ G when transforming G into an ℐ -lca-relevant DAG H , it often happens that certain clusters in ℭ G do not appear as clusters in H . To understand this phenomenon in detail, we characterize the subset of clusters in ℭ G that remain in H for DAGs G with the ℐ -lca-property. Furthermore, we show that the set W of vertices required to transform G into H = G ⊖ 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 ℭ G represents the clustering system of a tree or galled-tree and G has the ℐ -lca-property. In the latter case ℭ H = ℭ G always holds.