Irrelevant Components and Exact Computation of the Diameter Constrained Reliability

Let G = (V,E) be a simple graph with |V | = n nodes and |E | = m links, a subset K ⊆ V of terminals, a vector p = (p1,..., pm) ∈ [0, 1]m and a positive integer d, called diameter. We assume nodes are perfect but links fail stochastically and independently, with probabilities qi = 1 − pi. The diameter-constrained reliability (DCR for short), is the probability that the terminals of the resulting subgraph remain connected by paths composed by d links, or less. This number is denoted by RdK,G(p). The general computation of the parameter RdK,G(p) belongs to the class of NP-Hard problems, since is subsumes the complexity that a random graph is con-nected. A discussion of the computational complexity for DCR-subproblems is provided in terms of the number of terminal nodes k = |K | and diameter d. Either when d = 1 or when d = 2 and k is fixed, the DCR is inside the class P of polynomial-time problems. The DCR turns NP-Hard eve