Network reliability and acyclic orientations

Let G = ( V, E ) be an undirected graph with V = n perfectly reliable vertices and E = m edges that work with probability p e and fail with probability q e for all e /in E . The network reliability problem considered here is to calculate R K [ G ] = Prob [there exists a path of working edges between every pair of a set K of k vertices]. Backtrack algorithms for this problem are presented. The complexity of these algorithms is discussed when applied to the all‐terminal network reliability problem where K = V . Strategies are presented which minimize the size of the search structures generated. The main theorems state that when these strategies are used, the size of the search structures may be measured by counting spanning trees or acyclic orientations.