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.
Uniformly sampling from cycles of a graph
graph theory;sampling
Exponential-time algorithmOne (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 cyclesCounting 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.