# FPRAS to estimate the probability to get a cyclic subgraph of a directed graph

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.