Cheap and Secure Web Hosting Provider : See Now

Uniformly sampling from cycles of a graph

, , No Comments
Problem Detail: 

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.

Asked By : Guillermo Angeris
Answered By : D.W.

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 http://cstheory.stackexchange.com/q/20246/5038.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61180

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback