Anna Lindeberg: Simplify DAGs via least common ancestor constraints

Ancestral relationships between known taxa - species or genes - can be represented by rooted trees, or more generally, by directed acyclic graphs (DAGs) where the taxa correspond to the leaves and inner vertices to evolutionary events. Both from the biological and computational point of view, it is desirable that these DAGs contain no redundant information, i.e., each vertex captures some feature of the data available on the taxa. In this talk, we consider a vertex "supported by the data" if it is a least common ancestor (LCA) of at least some set of taxa. We will see characterizations of so called LCA-relevant DAGs, that is, DAGs in which every vertex is an LCA of some subset of leaves. Furthermore, we will explore a simple 'ominus'-operation that can be applied to efficiently transform any given DAG into an LCA-relevant version, whilst maintaining crucial structural properties of the input. In particular, there are interesting connections between LCA-relevant DAGs and the collection of sets obtained by associating each vertex with its set of descendant leaves. Based on joint work with Marc Hellmuth, see https://arxiv.org/abs/2411.00708.