International Journal of Mathematics and Mathematical Sciences
Volume 2004 (2004), Issue 29-32, Pages 1551-1562
doi:10.1155/S016117120430623X

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

Abstract

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, RK(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 RK(G,D) is NP-hard, as this measure subsumes the classical K-terminal reliability RK(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.