Abstract:
We improve the time for approximating network (un)reliability to (n2). We do so not with a new algorithm, but with a deeper analysis and tweaking of algorithms from our previous work. In particular, we show that once a graph’s failure probability shrinks below 1/2, the graph rapidly transitions to a regime where even the expected number of cut failures is small, and in fact is almost exactly the same as the graph’s failure probability. That is, we are very unlikely to ever see more than one cut fail. This lets us treat these cut failures as essentially independent, making it easier to estimate their likelihood. The contribution of this paper is not just the improved time bound, but also this clearer understanding of the evolution of a graph’s reliability. Our results rely on some new methods for analyzing the distribution of cut failures conditioned on the failure of a particular cut, as well as new insights into the evolution of a graph’s connectivity as edges are randomly added over time. Some of our results apply more broadly, to all monotone reliability systems.
