Chip firing and all-terminal network reliability bounds

The (all-terminal) reliability   of a graph GG is the probability that all vertices are in the same connected component, given that vertices are always operational but edges fail independently each with probability pp. Computing reliability is #P-complete, and hence is expected to be intractable. Consequently techniques for efficiently (and effectively) bounding reliability have been the major thrust of research in the area. We utilize a deep connection between reliability and chip firings on graphs to improve previous bounds for reliability.