Diameter Constrained Reliability of Ladders and Spanish Fans

Héctor Cancela, Franco Robledo, Pablo Romero, Pablo Sartor

Abstract: We are given a graph $G = (V,E)$, terminal set $K \subseteq V$ and diameter $d$ > 0. Links fail stochastically and independently with known probabilities. The diameter-constrained reliability (DCR for short) is the probability that the $K$-diameter is not greater than $d$ in the subgraph induced by non-failed links. The contributions of this paper are two-fold. First, the computational complexity of DCR-subproblems is discussed in terms of the number of terminals $k$ = |$K$| and diameter $d$. Here, we prove that if $d$ > 2, the problem is NP-Hard when $K = V$, and second, we compute the DCR efficiently for ladders and Spanish fans.