Exact-Size Sampling of Enriched Trees in Linear Time

Abstract

We create a novel connection between Boltzmann sampling methods and Devroye's algorithm to develop highly efficient sampling procedures that generate objects from important combinatorial classes with a given size n in expected time O(n). This performance is best possible and significantly improves the state of the art for samplers of subcritical graph classes (such as cactus graphs, outerplanar graphs, and series-parallel graphs), subcritical substitution-closed classes of permutations, Bienaymé-Galton-Watson trees conditioned on their number of leaves, and several further examples. Our approach allows for this high level of universality, as it applies in general to classes admitting bijective encodings by so-called enriched trees, which are rooted trees with additional structures on the offspring of each node.