An unbiased pointing operator for unlabeled structures, with applications to counting and sampling
By Manuel Bodirsky, Eric Fusy, Mihyun Kang, and Stefan VigerskeIn: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA07), pages 356-365
Abstract
We introduce a general method to count and randomly sample unlabeled combinatorial structures. The approach is based on pointing unlabeled structures in an ``unbiased'' way, i.e., in such a way that a structur e of size n gives rise to $n$ pointed structures. We develop a specific Polya theory for the corresponding pointing operator, and present a sampling framework relying both on the principles of Boltzmann sampling and on Polya operators. Our method is illustrated on several examples: in each case, we provide enumerative results and efficient random samplers. The approach applies to unlabeled families of plane and non-plane unrooted trees, and tree-like structures in general, but also to cactus graphs, outerplanar graphs, RNA secondary structures, and classes of planar maps.
Deutsch