The complexity of computing the 2-K-reliability in networks

• We study the complexity of the diameter-constrained K-network reliability problem.
• We show that it can be solved in time linear in the number of nodes.
• A formulation is given based on combinatorial structures.

Consider a communication network composed by sites that never fail and links between them that fail independently from each other. In any instant, every link (x,y)(x,y) is operational or failed according to known probabilities p(xy)p(xy) and 1−p(xy)1−p(xy). Let d be any positive integer. Computing the probability that a fixed subset K of sites is connected with paths of length not higher than d (considering only non-failing links) is known as the d-DCKR (d-diameter constrained K-reliability) problem. Its general case is known to belong to the NP-hard complexity class; there are a number of particular cases whose complexity remains undetermined. In this paper we show that the computational complexity of the d  -DCKR is linear in the number of sites of the network when d=2d=2 and |K||K| is fixed (i.e. when |K||K| is not an input but a parameter of the problem).