{"id":"arxiv/2602.08471","url":"https://arxiv.org/abs/2602.08471","tags":["cs.DS","cs.DM","math.CO"],"score":0,"title":"Boltzmann sampling and optimal exact-size sampling for directed acyclic graphs","domain":"cs.DS","source":"arxiv","authors":["Wojciech Gabryelski","Zbigniew Gołȩbiewski","Martin Pépin"],"reviews":0,"subject":"cs.DS","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-02-09","reactions":{}}