A LINEAR-TIME ALGORITHM FOR COMPUTING K-TERMINAL RELIABILITY IN SERIES-PARALLEL NETWORKS*

Abstract. Let G (V, E) be a graph whose edges may fail with known probabilities and let K _ V be specified. The K-terminal reliability of G, denoted R(GK), is the probability that all vertices in K are connected. Computing R(G:) is, in general, NP-hard. For some series-parallel graphs, R(Gn) can be computed in polynomial time by repeated application of well-known reliability-preserving reductions. However, for other series-parallel graphs, depending on the configuration of K, R(Gn) cannot be computed in this way. Only exponential-time algorithms as used on general graphs were known for computing R(G<) for these "irreducible " series-parallel graphs. We prove that R(Gn) is computable in polynomial time in the irreducible case, too. A new set of reliability-preserving "polygon-to-chain " reductions of general applicability is introduced which decreases the size of a graph, and conditions are given for a graph admitting such reductions. Combining all types of reductions, an O(IEI) algorithm is presented for computing the reliability of any series-parallel graph irrespective of the vertices in K