Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling

Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70’s by Robinson.

In this talk, I will introduce a new class of DAGs (DOAGs for Directed Ordered Acyclic Graphs), endowed with an independent ordering of the children of each vertex. They offer a new modelisation tool for objects arising from the compaction of tree-like structures.

For this class we obtain a recursive decomposition scheme that is amenable to effective random sampling with control over the number of edges, an optimised sampler for the case when the number of edges is free, and prove an unusual asymptotic behaviour. I will also show that our approach also applies to classical DAGs, thus providing a solution to the problem of sampling DAGs with a prescribed number of edges.