Consider a directed graph $G = (V, E)$ whose edges are annotated with independent probabilities of existence. This gives a probability distribution on the subgraphs of $G$; for instance, if each edge has probability $1/2$ and there are $m$ edges then all $2^m$ subgraphs are equally likely.
I'm interested in the probability of getting a subgraph which is cyclic, i.e., contains a directed cycle. Is there an FPRAS for this task, i.e., an algorithm polynomial in the graph and desired precision?
For context:
- There has been some study of the $s,t$-reliability problem, where there are distinguished vertices $s$ and $t$ and we want to know the probability of getting a subgraph where there is a directed path from $s$ to $t$. There, computing the exact probability is #P-hard and it is a longstanding open question whether a FPRAS exists. But I don't know of a reduction from my problem to $s,t$-reliability or vice-versa.
- Exact computation of my problem, i.e., computing the exact probability to get a cyclic subgraph, is #P-hard too. Indeed, the $s,t$-reliability problem is #P-hard to solve exactly, already on DAGs, so we can reduce from that problem simply by taking a DAG and adding an edge with probability 1 going back from $t$ to $s$.
- I also don't know the status of the problem where, given the probabilistic directed graph $G$, we are also given $n$ and want to approximate the probability of getting a directed (not necessarily simple) path of length $n$ (in particular a cycle). The cycle problem is a special case of that problem, where the input $n$ is larger than the number of vertices so the only way to get a sufficiently long path is to have a cycle. So that problem with directed paths is more general -- maybe it is easier to show that it does not admit an FPRAS.
Source: this is an open problem from a recent joint paper.
