2026-07-22T06:49:37Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18711 2024-03-06T11:02:32Z ddc:004 open_access

Counting and Sampling Labeled Chordal Graphs in Polynomial Time Hébert-Johnson, Úrsula Lokshtanov, Daniel Vigoda, Eric Counting algorithms graph sampling chordal graphs We present the first polynomial-time algorithm to exactly compute the number of labeled chordal graphs on n vertices. Our algorithm solves a more general problem: given n and ω as input, it computes the number of ω-colorable labeled chordal graphs on n vertices, using O(n⁷) arithmetic operations. A standard sampling-to-counting reduction then yields a polynomial-time exact sampler that generates an ω-colorable labeled chordal graph on n vertices uniformly at random. Our counting algorithm improves upon the previous best result by Wormald (1985), which computes the number of labeled chordal graphs on n vertices in time exponential in n. An implementation of the polynomial-time counting algorithm gives the number of labeled chordal graphs on up to 30 vertices in less than three minutes on a standard desktop computer. Previously, the number of labeled chordal graphs was only known for graphs on up to 15 vertices. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Úrsula Hébert-Johnson and Daniel Lokshtanov and Eric Vigoda 2023 Is Part Of LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2023.58 urn:nbn:de:0030-drops-187119 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.58 eng https://creativecommons.org/licenses/by/4.0/legalcode