Reliability of communication networks with delay constraints: computational complexity and complete topologies

Let G = ( V , E ) be a graph with a distinguished set of terminal vertices K ⫅ V . We define the K -diameter of G as the maximum distance between any pair of vertices of K . If the edges fail randomly and independently with known probabilities (vertices are always operational), the diameter-constrained K-terminal reliability of G , R K ( G , D ) , is defined as the probability that surviving edges span a subgraph whose K -diameter does not exceed D . In general, the computational complexity of evaluating R K ( G , D ) is NP-hard, as this measure subsumes the classical K -terminal reliability R K ( G ) , known to belong to this complexity class. In this note, we show that even though for two terminal vertices s and t and D = 2 , R { s , t } ( G , D ) can be determined in polynomial time, the problem of calculating R { s , t } ( G , D ) for fixed values of D , D ≥ 3 , is NP-hard. We also generalize this result for any fixed number of terminal vertices. Although it is very unlikely that general efficient algorithms exist, we present a recursive formulation for the calculation of R { s , t } ( G , D ) that yields a polynomial time evaluation algorithm in the case of complete topologies where the edge set can be partitioned into at most four equi-reliable classes.