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?
Percolation probabilities
graph theory;approximation algorithms;pr.probability;statistical physics