Department Seminar of Prof. David Karger, Fast and Simple Algorithms for All-Terminal Network Reliability
Speaker: Prof. David Karger, EECS Department, MIT
Sunday, June 26, 2022
Fast and Simple Algorithms for All-Terminal Network Reliability
The all-terminal network reliability problem asks to compute, for a given graph $G$, the probability that graph becomes disconnected when all edges fail independently with some probability. This fundamental problem in graph theory and reliability has been studied for decades, with the first fully polynomial randomized approximation scheme (FPRAS) given in 1995.
In this work, I will describe a particularly simple polynomial time algorithm for this problem, with an equally simple proof of correctness. It relies on generating a low variance unbiased estimator using "partially sampled" graphs, then estimating their reliability recursively. The resulting algorithm is far simpler and much faster than the first one. The analysis introduces techniques that may be useful for a broader class of reliability problems.
I will then sketch more sophisticated techniques that can be used to improve the running time of this approximation scheme. In particular I will show that as the edge failure probability decreases there is a rapid "phase transition" from a regime where the graph is likely disconnected, to one in which all cuts can be treated as failing independently which dramatically simplifies the problem. The analysis relies on some new analysis of the Contraction Algorithm---a stochastic process of contracting randomly chosen graph edges until the graph has been fully collapsed.
David Karger (Ph.D. Stanford University 1994) is a professor of computer science in the EECS department at MIT, and a member of the Computer Science and Artificial Intelligence Laboratory. His early research focused on randomized algorithms for graph optimization problems, and has since broadened to encompass information retrieval, databases, networking, natural language processing, coding theory, and human-computer interaction. His work has won the SIGCOMM test of time award and the SIGIR test of time award. He is a fellow of the ACM and of the American Academy of Arts and Sciences.