The complexity of the K-reliability in networks constrained to diameter two

Abstract

Consider a communication network with a set of sites and a set of links between them. Suppose that the sites are perfect but the links can fail independently from one another. Suppose also that at any given instant t, every link xy is operational or failed with probabilities denoted by p(xy) and 1 - p(xy) respectively. Therefore, there is an \201Coperational subnetwork\201D composed by all the sites and only those links that are operational. Computing the network reliability, i.e. the probability that a given subset K of \201Cdistinguished\201D sites are connected on the operational network yielded at t is known as the K-reliability problem and has been widely studied [1]. When additionaly requiring that the operational network be d-K-connected (i.e. that the distance between any pair of sites of K be bounded by a positive integer d) the problem is known as ddiameter- constrained K-reliability (d-DCKR). In this case the reliability is denoted by Rk(G; d). First introduced in [2], this problem has recently gained relevance because it can model situations where limits exist on the acceptable delay times to propagate traffic (like in voice applications over IP networks) or in the amount of hops that packets can undergo (peer-to-peer networks). The general version is known to belong to the NP-hard complexity class [3]. In this paper we prove