<p>I have a finite undirected graph with a probability $p_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p_e$ independently of the others.</p>

<p>I'm interested in computing probabilities like the probability that some given subset of the graph is connected (in particular pairs of vertices). This seems hard to do exactly. Has it been proven to be hard? Are there approximation algorithms?</p>

<p>Also, I am interested in sampling from the distribution conditioned on certain subsets being connected (again, just conditioning on a pair of vertices being connected seems interesting enough). How to do this?</p>

CC BY-SA 3.0
2016-05-05T12:56:44.707Z
Does your graph have more structure?  The classical results are for the complete graph, and special cases that are easy to analyse like paths, barbells, or complete bipartite graphs.
András Salamon
CC BY-SA 3.0
2016-05-05T13:10:49.920Z
No, though any results on special cases are of interest. Since my probabilities are general, the complete graph contains all other graphs by letting some p_e's be 0.
crestmods
CC BY-SA 3.0
2016-05-05T15:28:05.587Z
I think you are asking too general a question.  A standard reference like the Bollobás book on random graphs doesn't even cover cases where the underlying space of graphs is not uniform.  On the other hand, Ising and other statistical physics models impose a strict lattice structure on the graph as it is intended to model real systems of interacting parts.  For a model as general as the one you posit, the best we have are simulations, and it is hard to draw general conclusions when there is metastability everywhere.
András Salamon
CC BY-SA 3.0
2016-05-05T17:31:58.057Z
Have a look at [Advanced Topics in Graph Theory: Random Graphs](http://www.cs.toronto.edu/~molloy/2427-11/index.html) course by Mike Molloy. There are many similar courses that you can find using Google.
Kaveh
CC BY-SA 3.0
2016-05-05T17:33:57.733Z
Another thing you might want to look at is Razborov's [flag algebras](http://people.cs.uchicago.edu/~razborov/files/flag.pdf).
Kaveh
CC BY-SA 3.0
2016-05-06T20:42:26.750Z
@AndrásSalamon : do you mean that the question is too general in the sense that these numbers are hard to compute? If they are, then that would be an answer to the question.
crestmods
CC BY-SA 3.0
2016-06-03T00:34:05.947Z
I think he said the question is too general because the answer varies a lot on the structure of the original graph.
Vinicius dos Santos
CC BY-SA 3.0
2016-06-19T19:35:15.393Z
The question remains!  The answer is either "here is an algorithm for all graphs [...]" or "here is a proof of NP-hardness for this subset of graphs [...], hence for all graphs".
crestmods
CC BY-SA 4.0
2018-10-25T22:08:14.090Z
The following reference gives a PTAS for the variant where you want all nodes to remain connected.  The paper also states that that variant is known to be #P-complete to solve exactly.  https://scholar.google.com/scholar?lookup=0&q=A+RANDOMIZED+FULLY+POLYNOMIAL+TIME+APPROXIMATION+SCHEME+FOR+THE+ALL+TERMINAL+NETWORK+RELIABILITY+PROBLEM&hl=en&as_sdt=0,22&as_vis=1
Neal Young
<graph-theory><approximation-algorithms><pr.probability><statistical-physics>
Percolation probabilities
crestmods
# Percolation probabilities

(Asked by: username_0 on 2016-05-05)

I have a finite undirected graph with a probability $p\_e$ given for each edge $e$. This gives a random graph by removing each edge e with probability $1-p\_e$ independently of the others.

I'm interested in computing probabilities like the probability that some given subset of the graph is connected (in particular pairs of vertices). This seems hard to do exactly. Has it been proven to be hard? Are there approximation algorithms?

Also, I am interested in sampling from the distribution conditioned on certain subsets being connected (again, just conditioning on a pair of vertices being connected seems interesting enough). How to do this?

**Tags:** graph-theory, approximation-algorithms, pr.probability, statistical-physics

> **Comments:**
> **username_1**: Does your graph have more structure?  The classical results are for the complete graph, and special cases that are easy to analyse like paths, barbells, or complete bipartite graphs.  
> **username_0**: No, though any results on special cases are of interest. Since my probabilities are general, the complete graph contains all other graphs by letting some p_e's be 0.  
> **username_1**: I think you are asking too general a question.  A standard reference like the Bollobás book on random graphs doesn't even cover cases where the underlying space of graphs is not uniform.  On the other hand, Ising and other statistical physics models impose a strict lattice structure on the graph as it is intended to model real systems of interacting parts.  For a model as general as the one you posit, the best we have are simulations, and it is hard to draw general conclusions when there is metastability everywhere.  
> **username_2**: Have a look at [Advanced Topics in Graph Theory: Random Graphs](http://www.cs.toronto.edu/~molloy/2427-11/index.html) course by Mike Molloy. There are many similar courses that you can find using Google.  
> **username_2**: Another thing you might want to look at is Razborov's [flag algebras](http://people.cs.uchicago.edu/~razborov/files/flag.pdf).  
> **username_0**: @AndrásSalamon : do you mean that the question is too general in the sense that these numbers are hard to compute? If they are, then that would be an answer to the question.  
> **username_3**: I think he said the question is too general because the answer varies a lot on the structure of the original graph.  
> **username_0**: The question remains!  The answer is either "here is an algorithm for all graphs [...]" or "here is a proof of NP-hardness for this subset of graphs [...], hence for all graphs".  
> **username_4**: The following reference gives a PTAS for the variant where you want all nodes to remain connected.  The paper also states that that variant is known to be #P-complete to solve exactly.  https://scholar.google.com/scholar?lookup=0&q=A+RANDOMIZED+FULLY+POLYNOMIAL+TIME+APPROXIMATION+SCHEME+FOR+THE+ALL+TERMINAL+NETWORK+RELIABILITY+PROBLEM&hl=en&as_sdt=0,22&as_vis=1  

---

## 0 answers

