Threshold Reliability of Networks with Small Failure Sets

Abstract

This paper addresses two classes of reliability analysis models: a network flow model and a project scheduling model. For the network flow model we are given a capacitated source/sink graph in which arcs fail randomly. The system is defined as operating whenever the max-flow value is greater than a threshold. For the project scheduling model we are given a directed acyclic source/sink graph in which each arc has two lengths. Each arc randomly takes on one of two states. In the "operating" state it takes on its smaller length and in its "failed" state it takes on it larger length. The system is defined as operating whenever the length of the longest path is less than a threshold. We address a special case of the threshold flow problem in which all arcs have the same capacity and a special case of the project scheduling model in which the difference between the lower and higher arc lengths is constant. For these special cases we show that if the underlying systems are 1-critical, namely, all arcs are in some cutset of size two, then the threshold flow problem can be solved in polynomial time and planar project scheduling problem can be solved in polynomial time. Both solutions are obtained by reducing the problems to the problem of determining the probability that the failed arcs in a directed acyclic graph lie on a single path. We also show how the basic approach can be used to generate bounds for systems that are "almost critical".