Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs
Abstract
We propose two efficient algorithms for generating uniform random directed acyclic graphs, including an asymptotically optimal exact-size sampler that performs $\frac{n^2}{2} + o(n^2)$ operations and requests to a random generator. This was achieved by extending the Boltzmann model for graphical generating functions and by using various decompositions of directed acyclic graphs. The presented samplers improve upon the state-of-the-art algorithms in terms of theoretical complexity and offer a significant speed-up in practice.
Fields of Study & Subjects
Graph Theory and Algorithms
Advanced Combinatorial Mathematics
Advanced Graph Theory Research
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 9 February 2026
- Language
- EN
- Document type
- Preprint