A factoring algorithm using polygon-to-chain reductions for computing k-terminal network reliability

Let G = (V,E) be an undirected graph whose edges may fail, and let G, denote G with a set K V specified. Edge failures are assumed to be statistically independent and to have known probabilities. The K-terminal reliability of G,, denoted R(G,), is the probability that all vertices in K are connected by working edges. Computing K-terminal reliability is an NP-hard problem not known to be in NP. A factoring algorithm for computing network reliability recursively applies the formula R(G,) = p,R(G,,*e,) + q,R(G,- e,) , where Gxr*e, is G, with edge e, contracted, G, - e, is G, with e, deleted and p, = I- q, is the reliability of edge e,. Various reliability-preserving reductions may be performed after each factoring operation in order to reduce computational complexity. The complexity of a slightly restricted factoring algorithm using standard reductions, along with newly developed polygon-to-chain reductions, will be bounded below by an invariant of G, the “minimum domination. ” For 2 5 (KI 5 5 or IVI- 2 5 IKI 5 IVI, this bound is always achievable. The factoring algorithm with polygon-to-chain reductions will always perform as well as or better than an algorithm using only standard reductions, and for some networks, it will outperform the simpler algorithm by an exponential factor. This generalizes early results that were only valid for K = V. Removing the restriction on edge selection leaves results essentially unchanged in the upper range of IK(, but minimum domination becomes only a tight upper bound for the lower range. 1