4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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:

  1. 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)$.)

  2. 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.

$\endgroup$
  • $\begingroup$ Overall, iirc, it's hard to estimate the number of simple cycles (doing it within some factor I believe is NP-hard) so I think you may be right---if there's a PTAS to estimate the distribution of cycles within some $\varepsilon$, then we can estimate the number of cycles of length $k$ to within $O\left(\frac{N!}{(N-k)!2k}\varepsilon\right)$. $\endgroup$ – Guillermo Angeris Aug 2 '16 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.