Problems / algorithms-optimization

algorithms-optimization / Randomized algorithms

Approximating Two-Terminal Network Reliability

Does two-terminal reliability, the probability that $s$ still reaches $t$ when edges fail independently, admit a fully polynomial-time randomised approximation scheme? Asked explicitly in Kannan's 1994 survey and left open while the all-terminal cases were settled by Karger and by Guo and Jerrum. Answered positively for general graphs, both directed and undirected. The complementary unreliability question is shown to be BIS-hard, so it is unlikely to admit one.