Approximation of two-terminal network reliability
Follow the latest progress by email.
In a directed graph whose edges independently open with given probabilities, can the probability of an open path from s to t be approximated in randomized polynomial time?
Why it matters and what counts as progress
Why it matters: The problem asks for efficient relative approximation of a probability whose exact computation is #P-complete.
What counts as progress: A fully polynomial randomized approximation scheme for general directed graphs, including graphs with cycles, with the undirected extension justified by reduction.
How the problem developed
- 1979 · Hardness result [1]
Leslie G. Valiant Introduced two-terminal network reliability among the early counting problems shown #P-complete, motivating approximate rather than exact algorithms.
- 2024 · Algorithm [2]
Weiming Feng and Heng Guo Gave an FPRAS for two-terminal reliability on directed acyclic graphs, a restricted graph class.
- 3 Aug 2026 · Reported claim [1]
Weiming Feng, Yucheng Fu and Heng Guo, with GPT-5.6 Sol Ultra Gave an FPRAS for two-terminal reliability on general directed and undirected graphs and proved complementary unreliability #BIS-hard.
AI contribution
Approximating two-terminal network reliability
Feng, Fu and Guo give a fully polynomial randomized approximation scheme for s-to-t reachability probability in general directed graphs with independent edge-opening probabilities. An existing reduction extends it to undirected graphs.
Sources
Website timeline
Publication dates and editorial changes.