Algorithms for K-Terminal Reliability Problems with Node Failures

Consider a distributed processing system with a set K of sites that can either cooperate in computing a function or hold resources required by other sites. The system is implemented using a communication network with unreliable nodes. Two simplified reliability problems then arise. In the first problem, we are interested in computing the probability that every operational pair of sites in K can communicate with each other. This problem is known to be #P-complete. In the second problem, the sites in K are service centers. Our reliability measure is the probability that every operational site in the network is connected to at least one operational service center. In this paper, we define the class of t-polygon graphs, t ≥ 3, as the intersection graphs of straight line chords in a convex t-gon. Hence, any t-polygon graph is a circle graph. We show that both problems admit polynomial time solutions when the underlying graph of the network is restricted to a t-polygon graph, for a fixed t.