1. Sampling Unlabeled Chordal Graphs in Expected Polynomial Time
- Author
-
Hébert-Johnson, Úrsula and Lokshtanov, Daniel
- Subjects
Computer Science - Data Structures and Algorithms - Abstract
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{FPT}$ 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/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{FPT}$ 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., Comment: Accepted for publication at STACS 2025 (International Symposium on Theoretical Aspects of Computer Science); 14 pages
- Published
- 2025