In the network reliability problem, we are given an undirected graph $G$ on $n$ vertices and a parameter $p\in (0,1)$, and are tasked with determining the probability that $G$ becomes disconnected (i.e., some two nodes in the graph are not connected by a path) if we independently and randomly delete each edge of $G$ with probability $p$.

It is known that this problem is $\text{#P}$-hard, so it is unlikely to admit a polynomial-time algorithm.

Question: What is the fastest known (exact, not approximate) algorithm for solving network reliability?


1 Answer 1


This paper shows an exact mapping from reliability to exact model counting. From that point on, exact counters (like miniC2D) can be used to compute reliability. Not sure if useful runtime bounds exist for this scheme.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.