Sampling Unlabeled Chordal Graphs in
Expected Polynomial Time

The sampling algorithm of Wormald [20] is based on the fact that unlabeled graphs correspond to orbits of the following group action: the symmetric group $S_n$ acts on the set of labeled graphs by permuting the vertex labels. This correspondence follows from the Frobenius-Burnside lemma. Therefore, to sample a random unlabeled graph, it is enough to sample a random orbit of this group action.

To make this approach work for chordal graphs, we need two ingredients: (1) an algorithm for counting and sampling labeled chordal graphs with a given automorphism $\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.

For (1), we design an $\mathrm{𝖥𝖯𝖳}$ (fixed-parameter tractable) counting algorithm that is parameterized by $\mu$, the number of moved points of $\pi$. This algorithm uses $O(2^{7\mu }{n}^9)$ arithmetic operations. Using the standard sampling-to-counting reduction of [15], we also obtain a corresponding sampling algorithm with the same running time. Our main algorithm (for sampling unlabeled chordal graphs) calls each of these $\mathrm{𝖥𝖯𝖳}$ algorithms as a black box with potentially large values of the parameter $\mu$. Nevertheless, using the bound from (2), we are able to show that the probability of using a large value of $\mu$ is exponentially small, so the expected running time is not significantly affected.

To design the counting algorithm for (1), we rewrite each of the recurrences from the algorithm of Hébert-Johnson et al., now carrying around information about the automorphism $\pi$ and its moved points. The original algorithm is a dynamic-programming algorithm in which there is a constant number of types of vertices ($X$, $L$, etc.) in each graph that we wish to count. In our updated version, we now keep track of the type of each vertex that is moved by $\pi$.

To prove the bound for (2), we distinguish between the cases when $\mu$ is small and $\mu$ is large ($\mu$ is either less than or greater than $\frac{n}{d\log n}$, where $d$ is a constant). When $\mu$ is small, we use the fact that almost every chordal graph is a split graph [1], and we strengthen this by showing that in fact, almost every chordal graph is a balanced split graph. For the case of balanced split graphs, the argument is easy and is similar to the proof of the bound for general graphs [16]. When $\mu$ is large, the argument is more complicated. We observe that the vast majority of $n$-vertex labeled chordal graphs have maximum clique size close to $n/2$. Along the way, we also use the fact that for every chordal graph $G$, there exists a PEO (perfect elimination ordering) of $G$ such that some maximum clique appears at the tail end of that PEO.

For $n\in \mathbb{N}$, let $S_n$ denote the group of all permutations of $[n]$. For a permutation $\pi \in S_n$, we define $M_{\pi }≔\{i\in [n]:\pi (i)\ne i\}$ to be the set of points moved by $\pi$. For $n\in \mathbb{N}$, ${[n]}_0≔\{0,2,3,\mathrm{\dots },n\}$ denotes the set of all possible values of $|M_{\pi }|$ for $\pi \in S_n$.

Suppose $\pi \in S_n$, $C\subseteq [n]$. We write $\pi (C)≔\{\pi (i):i\in C\}$ to denote the image of $C$ under $\pi$. We say $C$ is invariant under $\pi$ if $\pi (i)\in C$ for all $i\in C$. For a set $C$ that is invariant under $\pi$, we write ${\pi |}_C$ to denote the permutation $\pi$ restricted to the domain $C$.

A labeled graph is a pair $G=(V,E)$, where the vertex set $V$ is a finite subset of $\mathbb{N}$ and the edge set $E$ is a set of two-element subsets of $V$. For a permutation $\pi \in S_n$ and a labeled graph $G$ such that $V(G)\subseteq [n]$ is invariant under $\pi$, we say ${\pi |}_{V(G)}$ is an automorphism of $G$ if for all $u,v\in V(G)$, $u$ and $v$ are adjacent if and only if $\pi (u)$ and $\pi (v)$ are adjacent.

A vertex $v$ in a graph $G$ is simplicial if its neighborhood $N(v)$ is a clique. A perfect elimination ordering (PEO) of a graph $G$ is an ordering $v_1,\mathrm{\dots },v_n$ of the vertices of $G$ such that for all $i\in [n]$, $v_i$ is simplicial in the subgraph induced by the vertices $v_i,\mathrm{\dots },v_n$. A graph is chordal if and only if it has a perfect elimination ordering [3]. The following two lemmas are well-known facts about chordal graphs. The proof of the first can be found in [3].

Our algorithm for counting the number of labeled chordal graphs with a given automorphism will use the notion of evaporation sequences from [14].

Suppose we are given a chordal graph $G$ and a clique $X\subseteq V(G)$. The evaporation sequence of $G$ with exception set $X$ is defined as follows: If $X=V(G)$, then the evaporation sequence of $G$ is the empty sequence. If $X⊊V(G)$, then let ${\tilde{L}}_1$ be the set of all simplicial vertices in $G$, and let $L_1={\tilde{L}}_1\setminus X$. Suppose $L_2,\mathrm{\dots },L_t$ is the evaporation sequence of $G\setminus L_1$ (with exception set $X$). Then $L_1,L_2,\mathrm{\dots },L_t$ is the evaporation sequence of $G$. As is shown in [14], the fact that $X$ is a clique implies that all vertices outside of $X$ eventually evaporate, so this is well-defined.

If the evaporation sequence $L_1,L_2,\mathrm{\dots },L_t$ of $G$ has length $t$, then we say $G$ evaporates at time $t$ with exception set $X$, and $t$ is called the evaporation time. We define $L_G(X)≔L_t$ to be the last set in the evaporation sequence of $G$, and we let $L_G(X)=\mathrm{\varnothing }$ if the sequence is empty. Similarly, we define the evaporation time of a vertex subset. Suppose $G$ has evaporation sequence $L_1,L_2,\mathrm{\dots },L_t$ with exception set $X$, and suppose $S\subseteq V(G)\setminus X$ is a nonempty vertex subset. Let $t_S$ be the largest index $i$ such that $L_i\cap S\ne \mathrm{\varnothing }$. We say $S$ evaporates at time $t_S$ in $G$ with exception set $X$.

Let $\text{Count\_Chordal\_Lab}(n)$ stand for the counting algorithm in [14] that computes the number of $n$-vertex labeled chordal graphs. In the full version of the paper, we prove the following two theorems.

See Section 4 for the details of the counting algorithm of Theorem 6 along with some intuition behind the proof of correctness. In our algorithm for sampling unlabeled chordal graphs, $\text{Count\_Chordal\_Lab}(n,\pi )$ stands for the algorithm of Theorem 6 and $\text{Sample\_Chordal\_Lab}(n,\pi )$ stands for the algorithm of Theorem 7.

Recall that ${[n]}_0=\{0,2,3,\mathrm{\dots },n\}$. For $\mu \in {[n]}_0$, let $R_{\mu }≔\{\pi \in S_n:|M_{\pi }|=\mu \}$ be the set of permutations with exactly $\mu$ moved points. For $\pi \in S_n$, let $\text{Fix}(\pi )$ denote the set of $n$-vertex labeled chordal graphs $G$ such that $\pi$ is an automorphism of $G$. To follow the same approach as the algorithm of Wormald, for each $\mu \in {[n]}_0$, we need an upper bound $B_{\mu }$ that satisfies $B_{\mu }\ge |R_{\mu }||\text{Fix}(\pi )|$ for all $\pi \in R_{\mu }$. Let $B_0$ be the number of $n$-vertex labeled chordal graphs, which is exactly equal to $|R_0||\text{Fix}(\text{id})|$. For $2\le \mu \le \frac{n}{200\log n}$, let

and for , let

where $f(\mu )=\frac{{\mu }^2}{900}-\frac{\mu }{10}$. In Section 3.2, we will prove that we indeed have $B_{\mu }\ge |R_{\mu }||\text{Fix}(\pi )|$ for all $\pi \in R_{\mu }$, when $n$ is sufficiently large. Let $B={\sum }_{\mu \in {[n]}_0}{B}_{\mu }$.

Our algorithm for sampling a random $n$-vertex unlabeled chordal graph is given in Algorithm 1. The general idea is as follows. For $\mu \in {[n]}_0$, let ${\mathrm{\Gamma }}_{\mu }=\{(\pi ,G)\in {\mathrm{\Gamma }}_{\text{chord}}:|M_{\pi }|=\mu \}$. We choose $\mu$ such that the probability of each value of $\mu$ is $B_{\mu }/B$, which is approximately equal to ${\mathrm{\Gamma }}_{\mu }/{\mathrm{\Gamma }}_{\text{chord}}$. (We do not know how to efficiently compute the exact value of ${\mathrm{\Gamma }}_{\mu }/{\mathrm{\Gamma }}_{\text{chord}}$ since we do not know the exact number of unlabeled chordal graphs.) Since $B_{\mu }/B$ is not exactly equal to ${\mathrm{\Gamma }}_{\mu }/{\mathrm{\Gamma }}_{\text{chord}}$, we adjust for this by restarting with a certain probability in Step 11. We then proceed to select a random pair $(\pi ,G)\in {\mathrm{\Gamma }}_{\mu }$, and we output the graph $G$ without labels.

Step 10 can easily be implemented in $O(n)$ time in the following way. If $\mu =0$, let $\pi =\text{id}$. For $\mu \ge 2$, we can repeatedly choose a random permutation of $[\mu ]$ until we obtain a derangement. The expected number of trials for this is a constant (see [20]).

In Step 11, to compute $|R_{\mu }|$, we observe that $|R_0|=1$ and $|R_{\mu }|=!\mu \left(\genfrac{}{}{0pt}{}{n}{\mu }\right)$ for $\mu \ge 2$. Here $!\mu$ is the number of derangements of $\mu$. We compute $!\mu$ using the formula $!m=m!{\sum }_{i=0}^m{(-1)}^i/i!$ for $m\in \mathbb{N}$, which can be derived using the inclusion-exclusion principle.

The correctness of $\text{Count\_Chordal\_Lab}(n,\pi )$ and $\text{Sample\_Chordal\_Lab}(n,\pi )$ is proved in the full version of the paper.

We need to show that the output graph is chosen uniformly at random. One “iteration” refers to one run of Steps 9 to 11 or 9 to 14. In a given iteration, we say the pair $(\pi ,G)$ was “chosen” if $\pi$ was chosen from $R_{\mu }$ and $G$ was chosen by $\text{Sample\_Chordal\_Lab}(n,\pi )$. We claim that for all $(\pi ,G)\in {\mathrm{\Gamma }}_{\text{chord}}$, in any given iteration, the probability that $(\pi ,G)$ is chosen is $1/B$. Indeed, this probability is equal to

where $\mu =|M_{\pi }|$, since the probability of choosing $G$ in Step 12 is $1/|\text{Fix}(\pi )|$. Therefore, we output all $n$-vertex unlabeled chordal graphs with equal probability.

Next, we need to show that $B_{\mu }\ge |R_{\mu }||\text{Fix}(\pi )|$ for all $\pi \in R_{\mu }$ to verify that the probability $|R_{\mu }||\text{Fix}(\pi )|/B_{\mu }$ in Step 11 is at most 1. When $\mu =0$ this is an equality, so suppose $\mu \ge 2$. Clearly $|R_{\mu }|\le n^{\mu }\mu !$, so we just need to prove that the number of $n$-vertex labeled chordal graphs with automorphism $\pi$ is at most $B_{\mu }/(n^{\mu }\mu !)$ for all $\pi \in S_n$ with $\mu$ moved points.

In the case when $B_{\mu }$ is defined according to Equation 2, this follows from Theorem 8. The proof this theorem can be found in the full version of the paper. (The bound in Theorem 8 is in fact true for all values of $\mu$ – the reason why we define $B_{\mu }$ differently for smaller values of $\mu$ will become clear when we discuss the running time in Section 3.3.)

For the other case, suppose $2\le \mu \le \frac{n}{200\log n}$, and suppose $\pi \in S_n$ is a permutation with $\mu$ moved points. We need to show that the number of $n$-vertex labeled chordal graphs with automorphism $\pi$ is at most $B_{\mu }/(n^{\mu }\mu !)$. We begin by reducing to the case of split graphs. A split graph is a graph whose vertex set can be partitioned into a clique and an independent set, with arbitrary edges between the two parts. It is easy to see that every split graph is chordal. Furthermore, the following result by Bender et al. [1] shows that a random $n$-vertex labeled chordal graph is a split graph with probability $1-o(1)$.

Applying this proposition with $\alpha =\frac{9}{10}$ tells us that the number of $n$-vertex labeled chordal graphs that are not split is at most $B_0{\left(\frac{9}{10}\right)}^n$. To bound the number of $n$-vertex labeled split graphs with automorphism $\pi$, we consider two cases: balanced split graphs and unbalanced split graphs. We say a partition of the vertex set of a split graph $G$ is a split partition if it partitions $G$ into a clique and an independent set; i.e., a split partition is a partition that demonstrates that $G$ is split. We denote a split partition that consists of the clique $C$ and the independent set $I$ by the ordered pair $(C,I)$. We say an $n$-vertex split graph is balanced if $|C|\ge \frac{n}{3}$ and $|I|\ge \frac{n}{3}$ for every split partition $(C,I)$ of $G$. It is easy to bound the number of unbalanced split graph as follows.

The running time of Steps 1-6 is $O(n^7)$ arithmetic operations since that is the running time of $\text{Count\_Chordal\_Lab}(n)$. In this section, we will show that the rest of the algorithm uses only $O(n^7)$ arithmetic operations in expectation.

If we choose $\mu =0$ in Step 9 of Algorithm 1, then the algorithm is guaranteed to terminate in that iteration. Thus the expected number of iterations is at most $B/B_0$. Let $T$ be the expected running time of Algorithm 1 after completing Step 6 (this is where we choose $\mu$ at random and the loop begins). In Lemma 13, we show that $𝐄[T]$ is at most the product of $B/B_0$ and the expected running time of one iteration.

Let $N$ be the number of iterations of Algorithm 1, and let $T_j$ be the time spent in iteration $j$ for each $j\in [N]$. We have $T={\sum }_{j=1}^N{T}_j$.

For $k\in \mathbb{N}$, let $a(k)$ denote the number of labeled chordal graphs with vertex set $[k]$, and let $c(k)$ denote the number of connected labeled chordal graphs with vertex set $[k]$. The algorithm of [14] begins by reducing from counting chordal graphs to counting connected chordal graphs via the following recurrence, which appears as Lemma 3.13 in [14]. (We omit the “$\omega$-colorable” requirement since we will not need that here.)

Here $k^{\prime }$ stands for the number of vertices in the connected component that contains the label 1. The remaining connected components have a total of $k-k^{\prime }$ vertices. Since this recurrence is relatively simple, most of the difficulty in the algorithm of [14] lies in the recurrences for counting connected chordal graphs. However, when counting graphs with a given automorphism, the step of reducing to connected graphs is already quite a bit more involved.

Suppose we are given $n\in \mathbb{N}$ and $\pi \in S_n$ as input. From now on, whenever we refer to $n$ or $\pi$, we mean these particular values from the input.

We will first define $a(k,p,M)$ and $c(k,p,M)$, which are variations of $a(k)$ and $c(k)$ that only count graphs for which ${{\pi }^p|}_{V(G)}$ is an automorphism (see Definition 18). Here ${\pi }^p$ stands for $\pi$ to the power $p$, i.e., the permutation that arises from applying $\pi$ a total of $p$ times. The reason for raising $\pi$ to a power will be apparent in the recurrence for $a(k,p,M)$. In the initial, highest-level recursive call, we will have $p=1$ and thus ${\pi }^p=\pi$.

In [14], when counting the number of possibilities for a subgraph of size $k^{\prime }$ (for example, a connected component), the authors essentially relabel that subgraph to have vertex set $[k^{\prime }]$, so that one can count the number of possibilities using, for example, $c(k^{\prime })$. In our algorithm, we want to relabel the vertices of each subgraph in a similar way. However, this time, we do not relabel the vertices that are moved by $\pi$. This ensures that the automorphism in each later recursive call will still be $\pi$, or a permutation closely related to $\pi$.

As a consequence, the vertex sets of the subgraphs that we wish to count become slightly more complicated. For example, suppose we wish to count the number of possibilities for a 5-vertex subgraph that originally contains the moved vertices $2,8,9\in M_{\pi }$. Since we do not relabel the moved vertices, the resulting vertex set after relabeling is $\{1,2,3,8,9\}$ rather than $\{1,2,3,4,5\}$. More formally, suppose we have been given $k\in \mathbb{N}$ and $M\subseteq M_{\pi }$, where $|M|\le k$. Let $V$ be the set of the first $k-|M|$ natural numbers in $\mathbb{N}\setminus M_{\pi }$. We define $V_{k,M}≔V\cup M$. For example, if $k=5$ and $M=M_{\pi }=\{2,8,9\}$, then $V_{k,M}=\{1,2,3,8,9\}$. Intuitively, $V_{k,m}$ is the label set of size $k$ whose intersection with $M_{\pi }$ is $M$ and that otherwise contains labels that are as small as possible.

For $\widehat{\pi }\in S_n$ and $M\subseteq [n]$, recall that $M$ is invariant under $\widehat{\pi }$ if $\widehat{\pi }(i)\in M$ for all $i\in M$. For $M^{\prime },M\subseteq [n]$, we write $M^{\prime }{\subseteq }_{\widehat{\pi }}M$ to indicate that $M^{\prime }\subseteq M$ and $M^{\prime }$ is invariant under $\widehat{\pi }$. Intuitively, $M^{\prime }$ is a subset of $M$ that respects the cycles of $\widehat{\pi }$ by taking all or nothing of each cycle.

Our algorithm returns $a(n,1,M_{\pi })$. This is precisely the number of labeled chordal graphs with vertex set $[n]$ and automorphism $\pi$ since $V_{n,M_{\pi }}=[n]$.

Suppose we have been given fixed values of the arguments $k,p,M$ of $a(k,p,M)$. Let $s$ be the smallest label in the vertex set $V_{k,M}$. For $k^{\prime }\in [k]$, let ${𝒫}_{k^{\prime }}$ be the family of sets $M^{\prime }{\subseteq }_{{\pi }^p}M$ such that $|M|-k+k^{\prime }\le |M^{\prime }|\le k^{\prime }$ and such that the following condition holds: if $s\in M$, then $s\in M^{\prime }$, and otherwise, $|M^{\prime }|\le k^{\prime }-1$. This last condition will ensure that $s$ belongs to the connected component of size $k^{\prime }$ in the recurrence for $a(k,p,M)$.

Suppose $C\subseteq [n]$, $\sigma \in S_n$. For an element $i\in C$, we say the period of $i$ with respect to $(C,\sigma )$ is the smallest positive integer $j$ such that ${\sigma }^j(i)\in C$. Let $𝒬$ be the family of sets $C\subseteq M$ such that all elements of $C$ have the same period $j\ge 2$ with respect to $(C,{\pi }^p)$, and such that $s\in C$. For a set $C\in 𝒬$, we write $p_C$ to denote the period of the elements of $C$ (with respect to $(C,{\pi }^p)$), and we let $C_{\sigma }≔C\cup \sigma (C)\cup \mathrm{\cdots }\cup {\sigma }^{p_C-1}(C)$ denote the union of the sets that $C$ is mapped to by powers of $\sigma$, where $\sigma ={\pi }^p$.

To compute $a(k,p,M)$, we use the following recurrence. The dot in front of the curly braces denotes multiplication. Note that we have $|M^{\prime }|\le k^{\prime }$ and $|M\setminus M^{\prime }|\le k-k^{\prime }$ by the definition of ${𝒫}_{k^{\prime }}$.

For some intuition, suppose $G$ is a graph counted by $a(k,p,M)$, and let $C$ be the connected component of $G$ that contains $s$. The first line of the recurrence for $a(k,p,M)$ covers the case when $C$ is invariant under ${\pi }^p$. This case is analogous to Lemma 17. In the first summation, $k^{\prime }$ stands for $|C|$ and $M^{\prime }$ stands for the set of vertices in $C$ that can be moved by ${\pi }^p$. If $s\in M$, then in addition to the vertices in $M^{\prime }$, we need to choose $k^{\prime }-|M^{\prime }|$ additional vertices for $C$ so that $|C|=k^{\prime }$. For these, we must choose non-moved vertices, so there are $k-|M|$ possible vertices to choose from. If $s\notin M$, then we subtract 1 from each of the numbers in the binomial coefficient since we already know that $s$ is a non-moved vertex in $C$.

The second line covers the case when $C$ is not invariant under ${\pi }^p$, which means all of $C$ is mapped to some other connected component of $G$ by ${\pi }^p$. In this case, we have $p_C$ components of size $|C|$ that are all isomorphic to $C$, and the rest of the graph has $k-p_C|C|$ vertices. We do not need a binomial coefficient in this case because all of the vertices in $C$ are moved. There are $c(|C|,p\cdot p_C,C)$ possibilities for the edges of $C$ since ${\pi }^{p\cdot p_C}$ is an automorphism of $C$. As an example, suppose $p=1$. If we apply ${\pi }^p=\pi$ to the vertices of $C$ a total of $p_C$ times, then the image ${\pi }^{p_C}(C)$ is equal to $C$, although these two sets might not match up pointwise. To ensure that the image ${\pi }^{p_C}(C)$ matches up with the edges of $C$, we require that ${\pi }^{p_C}$ is an automorphism of $C$. This is why we need the argument $p$ in $a(k,p,M)$ and $c(k,p,M)$.

Note that for a graph $G$ counted by $a(k,p,M)$, we have $M_{{\pi }^p}\cap V(G)\subseteq M_{\pi }\cap V(G)\subseteq M$ since $V(G)=V_{k,M}$. This means no vertex in $V(G)\setminus M$ is moved by ${\pi }^p$, so we are free to relabel these vertices in the proof of Lemma 19 without changing the automorphism. In the initial recursive call $a(n,1,M_{\pi })$, we have $p=1$ and $M=M_{\pi }$, so $M_{{\pi }^p}\cap V(G)=M$. Later on in the algorithm, it is possible that some vertices in $M$ are not actually moved by ${\pi }^p$. For example, in the previous paragraph, it could happen that ${\pi }^{p\cdot p_C}$ is the identity on $C$ (and then $p\cdot p_C$ becomes the new value of $p$). However, we always have $M\subseteq M_{\pi }$ by the definition of $a(k,p,M)$, so if $|M_{\pi }|=\mu$, then $|M|\le \mu$. This fact will be useful for the running time analysis.

The proof of Lemma 19, along with the proofs of all of the following recurrences, can be found in the full version of the paper.

To compute $c(k,p,M)$, we will define various counter functions that are analogous to those in [14]. First, we recall the counter functions from [14]. We refer to functions 1-4 in Definition 20 as $g$-functions, and we refer to the others as $f$-functions. See Figure 1 in [14] for an illustration of all of these functions.