Full complexity analysis of the diameter-constrained reliability.

Abstract

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 DCR computation is inside the class of NP-Hard problems, since is subsumes the complexity that a random graph is connected. The contributions of this paper are two-fold. First, a full analysis of the computational complexity of DCR-subproblems is presented in terms of the number of terminal nodes k = |K| and diameter d. Second, we extend the class of graphs that accept efficient DCR computation. In this class we include graphs with bounded co-rank, graphs with bounded genus, planar graphs, and, in particular, Monma graphs, which are relevant in robust network design.