Duke Computer Science's Theory Group members are honored to have eight papers accepted at the January 2024 ACM-SIAM Symposium on Discrete Algorithms (SODA) conference, with six of the Duke CS papers co-written by our graduate students. Read a brief summary of one of these papers, "Beyond the Quadratic Time Barrier for Network Unreliability," below.
The unreliability of a network, defined as the probability that it disconnects under random (and independent) connection failures, is a natural measure of its robustness in real-world settings. Although the exact value of unreliability turns out to be computationally intractable, decades of research in this problem has resulted in a series of ever-more efficient algorithms that obtain approximations of unreliability to arbitrary precision. Of key importance is the observation that networks typically disconnect along vulnerable partitions, allowing an unreliability algorithm to enumerate these partitions while ignoring the well-connected regions.
But this has a natural limit — there can be quadratically-many minimum cuts, the most vulnerable of all partitions — resulting in the best unreliability algorithms having quadratic running times as a function of network size.
In our new paper, we give the first sub-quadratic-time algorithm for the network unreliability problem. The most striking feature of our algorithm is that it evaluates the impact of all the vulnerable partitions of the network, including all the minimum cuts, while spending time that is less than even the total number of minimum cuts. We achieve this by using a technique called importance sampling, which produces a random sample of how the network disconnects without enumerating the different ways of doing so. The sampling process is further guided by a "duality" framework, where the complementary problem of how the network can stay connected is used to understand how it can disconnect.
Our main technical work showcases the application of this duality-based importance sampling framework to estimate the unreliability of very reliable networks, usually the most difficult setting because of the elusiveness of the disconnection event. Beyond the application to network unreliability, we believe this new sampling framework is a promising tool for investigating other important properties of random networks.