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.