Given a graph G whose nodes are perfectly reliable and whose edges fail independently with probability q in [0,1], the all-terminal reliability of G is the probability that all vertices of G can communicate with one ...