 |
 |
25 of 32 |  |
 |
 |
MIT
Network Reliability
l
Suppose given G, p
l
Can we compute
Pr[
G(p)
disconnected]?
l
#P-complete
l
But: small cuts most likely to fail
»
Enumerate, using contraction algorithm
»
use DNF counting [KLM] to estimate
l
Result: fully polynomial randomized
approximation scheme