Approximating two-terminal network reliability
2026-08-03 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors developed a fast randomized algorithm that can closely estimate the two-terminal reliability of any graph, whether its edges have directions or not. This problem is about figuring out how likely it is that two points in a network remain connected despite failures. They also showed that calculating the exact probability that the connection fails is a computationally hard problem linked to another known hard problem, called BIS. The main idea for their algorithm was inspired by discoveries from GPT-5.6 Sol Ultra.
two-terminal reliabilityrandomized algorithmapproximation schemeFPRASdirected graphundirected graphBIS-hardgraph connectivitycomputational complexity
Authors
Weiming Feng, Yucheng Fu, Heng Guo
Abstract
We present a fully polynomial-time randomised approximation scheme (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. We also show that the complementary unreliability question is \BIS-hard. The key idea of the algorithm was discovered by GPT-5.6 Sol Ultra.