2026-07-21T19:24:55Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22872 2025-10-02T13:36:03Z ddc:004 open_access

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time Hébert-Johnson, Úrsula Lokshtanov, Daniel Chordal graphs graph sampling graph counting unlabeled graphs 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 π ∈ S_n is at most 1/2^{c max{μ²,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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Úrsula Hébert-Johnson and Daniel Lokshtanov 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.46 urn:nbn:de:0030-drops-228726 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.46 eng https://creativecommons.org/licenses/by/4.0/legalcode