Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling - Sorbonne Université
Conference Papers Year : 2021

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.
Fichier principal
Vignette du fichier
preprint.pdf (915.1 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03029381 , version 1 (28-11-2020)
hal-03029381 , version 2 (04-12-2020)

Identifiers

Cite

Antoine Genitrini, Martin Pépin, Alfredo Viola. Unlabelled ordered DAGs and labelled DAGs: constructive enumeration and uniform random sampling. The XI Latin and American Algorithms, Graphs and Optimization Symposium, May 2021, Sao Paulo, Brazil. pp.468-477, ⟨10.1016/j.procs.2021.11.057⟩. ⟨hal-03029381v2⟩
315 View
447 Download

Altmetric

Share

More