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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.