Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling

Abstract : Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. DAGs 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 many applications one needs to construct connected DAGs and to control their number of edges, but the adaptation of Robinson's enumeration to take this into account led to counting formulas based on the inclusion-exclusion principle, inducing a high computational cost for the uniform random sampling of DAGs based on this formula. In the present paper we propose two contributions. First we enumerate a new class of DAGs, enriched with an independent ordering of the children of each vertex, according to their numbers of vertices and edges. We obtain a constructive recursive counting formula for them (i.e. without using the inclusion-exclusion principle) using a new decomposition scheme. Then we show the applicability of our method by proposing a constructive enumeration of Robinson's labelled DAGs, by vertices and edges, based on the same decomposition. As a consequence we are able to derive efficient uniform random samplers for both models.
Complete list of metadatas

https://hal.sorbonne-universite.fr/hal-03029381
Contributor : Martin Pépin <>
Submitted on : Friday, December 4, 2020 - 2:48:29 PM
Last modification on : Friday, January 8, 2021 - 5:34:03 PM

File

preprint.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03029381, version 2

Citation

Antoine Genitrini, Martin Pépin, Alfredo Viola. Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling. 2020. ⟨hal-03029381v2⟩

Share

Metrics

Record views

19

Files downloads

25