Calculating K-Connectedness Reliability Using Steiner Bounds

The K-connectedness reliability problem considered in this paper has as input undirected graph G, subset K of terminal vertices, and common edge failure probability p, and as output the probability R(G, K, p) that—when edges fail independently each with probability p—the set of operating edges connect every pair of vertices of K. We show how the Steiner property held by the underlying simplicial complex associated with this problem can lead to an extension of the Ball-Provan shellability bounds to this more general problem. We show in computational studies that this bound performs quite favorably in comparison with known approximation techniques.