The network reliability problem ask one to determine the survival/failure probability of some terminals in a probabilistic network. In particular, the network is given as a graph, either directed or undirected. Each edge is associated with failure (survival) probability q_e (p_e = 1-q_e), which means it will fail (survive) with probability q_e (p_e). The problem ask you to compute the failure/survival rate of some terminals. The simplest version is s-t reliability, where the terminal sets contains only two terminals. Other variants include k-terminal and all-terminal reliability. The problem is known to be hard: it is #P-complete. It remains hard even when the graph is directed acyclic with maximum degree three. No computational effective methods exist unless P=NP. Hence people are interested in finding approximation algorithms.
Last semester I wrote an survey for the problem as a project in Approximation Algorithm course. The article introduces three methods for the problem, all of them utilize Monte-Carlo as the basic framework.
1. R. Karp and M. Luby's Monte Carlo [Karp and Luby]
R. Karp and M. Luby showed that Monte Carlo algorithm is an FPRAS (Fully polynomial time randomized approximation scheme) when the number of samples are sufficiently small. Furthermore, the number of samples are linear to the ratio of the size of positive samples and size of the sample space. Hence, how to formulate the sample space becomes the most important problem. They proposed several methods, which includes K-separating cuts, paths and cycles, and finally walks. The first two modeling is straightforward and easy to understand, however it utilized some false assumptions. The last one makes the Monte Carlo truly FPRAS. But personally I found it very hard to follow, and impractical.
2. Karger's alpha-Minimum Cut method [Karger FPRAS]
I have to say this is an interesting and clever method. First note that the network breaks only when the failure edges are in one of the cuts. He showed that only small cuts are vital when computing the failure probability. Here `small cuts' can be interpreted as the set of min cuts and `near' min cuts. In another Karger's paper, he showed that these cuts can be found can be found in polynomial time and the number is polynomial [Karger min cut] (very interesting algorithm, highly recommended). Hence, the problem can be reduced to DNF counting:
We assign a boolean variable xe to each edge e, where xe = true if e fails and false otherwise. For the ith small cut c_i, it disconnects the network if and only if all of its edges fail. Let F_i be the conjunction of all x_e, for all e in c_i. Clearly F_i is true if and only if c_i fails. Hence, the event that some small cuts fail can be written as F = disjunction of all F_i. We want to know the probability that F is true, which is clearly the failure probability of the network. Note that F is in disjunctive normal form, and the number of clauses in F is exactly the number of small cuts, which is a polynomial. There is a FPRAS for the DNF counting problem, which also uses Monte-Carlo. It is straight-forward now.
3. Zenklusen's FPRAS for s-t reliability problem on acyclic network [Zenklusen]
This is a relatively new result. The basic idea is, in a DAG, one can compute the mean number of intact path between s and t after the failure process. In a highly unreliable network, this number is a good estimate for the s-t reliability. Monte Carlo is used to estimate the ratio between reliability(s,t) and the mean number of intact s-t paths. He showed that the s-t paths can be sampled in linear time.
[Karp and Luby]: Monte-carlo algorithms for the planar multiterminal network reliability problem.
[Karger FPRAS]: A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem.
[Karger min cut]: An O~(n^2) algorithm for minimum cuts.
[Zenklusen]: Combinatorial methods for analyzing network security and reliability
----
I decided to release my manuscript from CS598: Approximation Algorithms, which is a survey on network reliability problem. I am not an expert on approximation algorithm, and my writing may not be so great. For any mysterious or unclear part, please refer to the original papers.
The file can be downloaded from
here. The password is 'cs598'. If this document is of any help, please give appropriate citation in your work.
