Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2501.05024 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
Inhaltsangabe:
- 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 $π$, 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 $π\in S_n$ is at most $1/2^{c\max\{μ^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 $\mathsf{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.