On computing the 2-diameter -constrained K -reliability of networks

This article considers a communication network modeled by a graph G=<V,E> and a distinguished set of terminal nodes K⊆V. We assume that the nodes never fail, but the edges fail randomly and independently with known probabilities. The classical K ‐reliability problem computes the probability that the subnetwork is composed only by the surviving edges in such a way that all terminals communicate with each other. The d ‐diameter ‐constrained K ‐reliability generalization also imposes the constraint that each pair of terminals must be the extremes of a surviving path of approximately d length. It allows modeling communication network situations in which limits exist on the acceptable delay times or on the amount of hops that packets can undergo. Both problems have been shown to be NP ‐hard, yet the complexity of certain subproblems remains undetermined. In particular, when d=2, it was an open question whether the instances with |K|>2 were solvable in polynomial time. In this paper, we prove that when d=2 and |K| is a fixed parameter (i.e. not an input) the problem turns out to be polynomial in the number of nodes of the network (in fact linear). We also introduce an algorithm to compute these cases in such time and also provide two numerical examples.