Uniform generation of random acyclic digraphs

Abstract

We show how to sample acyclic digraphs uniformly at random through recursive enumeration. This provides an exact method which avoids the convergence issues of the alternative Markov chain methods. The limiting behaviour of the distribution of acyclic digraphs also allows us to sample arbitrarily large acyclic digraphs. Finally we discuss how to include various restrictions in the combinatorial enumeration for efficient uniform sampling of the corresponding graphs.