Network Unreliability in Almost-Linear Time
The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability p. Valiant (1979) showed that this problem is #P-hard; therefore, the best we can hope for are approximation algorithms. In a classic result, Karger (1995) obtained the first FPRAS for this problem by leveraging the fact that when a graph disconnects, it almost always does so at a near-minimum cut, and there are only a small (polynomial) number of near-minimum cuts. Since then, a series of results have obtained progressively faster algorithms to the current bound of m1+o(1) + Õ(n3/2) (Cen, He, Li, and Panigrahi, 2024). In this paper, we obtain an m1+o(1)-time algorithm for the network unreliability problem. This is essentially optimal, since we need O(m) time to read the input graph. Our main new ingredient is relating network unreliability to an ideal tree packing of spanning trees (Thorup, 2001).
