Network Unreliability in Almost-Linear Time
October 29, 2025 (GHC 8102)

The network unreliability problem asks for the probability that a given undirected graph gets disconnected when every edge independently fails with a given probability. 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 FPTAS 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 a quadratic-time algorithm (Karger, 2020). In a prior work (Cen, He, Li, and Panigrahi, 2024), we improved the running time to $m^{1+o(1)} + \tilde{O}(n^{3/2})$. In this talk, I will discuss our recent result that obtains an almost-linear time algorithm for the network unreliability problem.