Sampling Unlabeled Chordal Graphs in Expected Polynomial Time

We design an algorithm that generates an $n$-vertex unlabeled chordal graph uniformly at random in expected polynomial time. Along the way, we develop the following two results: (1) an $\mathsf{F}\mathsf{P}\mathsf{T}$ algorithm for counting and sampling labeled chordal graphs with a given automorphism $\pi$, parameterized by the number of moved points of $\pi$, and (2) a proof that the probability that a random $n$-vertex labeled chordal graph has a given automorphism $\pi \in S_n$ is at most $1\mathrm{/}{2}^{c\max \{{\mu }^2,n\}}$, where $\mu$ is the number of moved points of $\pi$ and $c$ is a constant. Our algorithm for sampling unlabeled chordal graphs calls the aforementioned $\mathsf{F}\mathsf{P}\mathsf{T}$ algorithm as a black box with potentially large values of the parameter $\mu$, but the probability of calling this algorithm with a large value of $\mu$ is exponentially small.