patternMinor
Uniformly sampling from cycles of a graph
Viewed 0 times
uniformlygraphsamplingfromcycles
Problem
I was wondering if, given an arbitrary cycle basis (that's complete, e.g. every cycle in the graph can be expressed as the $\mathbb{Z}/2\mathbb{Z}$ sum of elements from the basis) of some graph $G$, is there some way of sampling all cycles uniformly? I'm not able to find papers on it, and I was wondering if anyone had any results on this.
Solution
Exponential-time algorithm
One (slow) approach is to rejection sampling.
Let $c_1,\dots,c_k$ be the cycle basis. Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$, where $\mathcal{E}$ is the set of Eulerian subgraphs of $G$, given by
$$\varphi(\alpha_1,\dots,\alpha_k) = \alpha_1 \cdot c_1 + \cdots + \alpha_k \cdot c_k.$$
This gives us a way to sample uniformly at random from the set of Eulerian subgraphs.
Note that the set $\mathcal{C}$ of simple cycles of $G$. Note that every simple cycle is an Eulerian subgraph, i.e., $\mathcal{C} \subseteq \mathcal{S}$. Thus, a simple procedure to sample uniformly at random from $\mathcal{C}$ is:
-
Sample uniformly at random from $\mathcal{E}$, to get a subgraph $e$. (Namely, pick $\alpha_1,\dots,\alpha_k$ uniformly at random and set $e = \varphi(\alpha_1,\dots,\alpha_k)$.)
-
If $e$ is a simple cycle, output it. Otherwise, go back to step 1.
This samples a simple cycle uniformly at random from the set of all simple cycles of $G$.
The (expected) running time is proportional to $|\mathcal{E}|/|\mathcal{C}|$. It is known that $|\mathcal{E}|=2^{|V|+|E|-1}$ if $G$ is connected. Thus, if $G$ has $C$ different cycles, this gives an algorithm whose running time is proportional to $2^{|V|+|E|-1}/C$. Depending on the number of cycles in $G$, this might be extremely slow.
I don't know if there is a polynomial-time algorithm or not.
Counting the number of simple cycles
Counting the exact number of simple cycles in a graph is NP-hard, by reduction from the Hamiltonian cycle problem. Jonathan Katz has some lecture notes that provide a proof.
I don't know whether it is hard to approximate the number of simple cycles in $G$. If it is, then this might imply hardness results for uniform sampling from among the set of simple cycles.
See also https://cstheory.stackexchange.com/q/20246/5038.
One (slow) approach is to rejection sampling.
Let $c_1,\dots,c_k$ be the cycle basis. Then we obtain an isomorphism $\varphi : (\mathbb{Z}/2\mathbb{Z})^k \to \mathcal{E}$, where $\mathcal{E}$ is the set of Eulerian subgraphs of $G$, given by
$$\varphi(\alpha_1,\dots,\alpha_k) = \alpha_1 \cdot c_1 + \cdots + \alpha_k \cdot c_k.$$
This gives us a way to sample uniformly at random from the set of Eulerian subgraphs.
Note that the set $\mathcal{C}$ of simple cycles of $G$. Note that every simple cycle is an Eulerian subgraph, i.e., $\mathcal{C} \subseteq \mathcal{S}$. Thus, a simple procedure to sample uniformly at random from $\mathcal{C}$ is:
-
Sample uniformly at random from $\mathcal{E}$, to get a subgraph $e$. (Namely, pick $\alpha_1,\dots,\alpha_k$ uniformly at random and set $e = \varphi(\alpha_1,\dots,\alpha_k)$.)
-
If $e$ is a simple cycle, output it. Otherwise, go back to step 1.
This samples a simple cycle uniformly at random from the set of all simple cycles of $G$.
The (expected) running time is proportional to $|\mathcal{E}|/|\mathcal{C}|$. It is known that $|\mathcal{E}|=2^{|V|+|E|-1}$ if $G$ is connected. Thus, if $G$ has $C$ different cycles, this gives an algorithm whose running time is proportional to $2^{|V|+|E|-1}/C$. Depending on the number of cycles in $G$, this might be extremely slow.
I don't know if there is a polynomial-time algorithm or not.
Counting the number of simple cycles
Counting the exact number of simple cycles in a graph is NP-hard, by reduction from the Hamiltonian cycle problem. Jonathan Katz has some lecture notes that provide a proof.
I don't know whether it is hard to approximate the number of simple cycles in $G$. If it is, then this might imply hardness results for uniform sampling from among the set of simple cycles.
See also https://cstheory.stackexchange.com/q/20246/5038.
Context
StackExchange Computer Science Q#61180, answer score: 2
Revisions (0)
No revisions yet.