2025/01/09 by Hébert-Johnson, Úrsula, Lokshtanov, Daniel
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2501.05024
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 FPT algorithm for counting and sampling labeled chordal graphs with a given automorphism π, parameterized by the number of moved points of π, and (2) a proof that the probability that a random n-vertex labeled chordal graph has a given automorphism π∈ Sn is at most 1/2^cmax\μ2,n\, where μ is the number of moved points of π and c is a constant. Our algorithm for sampling unlabeled chordal graphs calls the aforementioned FPT algorithm as a black box with potentially large values of the parameter μ, but the probability of calling this algorithm with a large value of μ is exponentially small.