Exact-Size Sampling of Enriched Trees in Linear Time
Konstantinos D. Panagiotou, Leon Ramzews, Benedikt Stufler · SIAM Journal on Computing · 2023
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 [Formula: see text] in expected time [Formula: see text]. 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.