Diameter Constrained Reliability: Computational Complexity in terms of the diameter and number of terminals

Let $G=(V,E)$ be a simple graph with $\mathrm{\mid }V\mathrm{\mid }=n$ nodes and $\mathrm{\mid }E\mathrm{\mid }=m$ links, a subset $K\subseteq V$ of \emph{terminals}, a vector $p=(p_1,\ldots,p_m) \in [0,1]^m$andapositiveinteger$d$, called \emph{diameter}. We assume nodes are perfect but links fail stochastically and independently, with probabilities $q_i=1-p_i$. The \emph{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 $R_{K,G}^d(p)$. The general DCR computation is inside the class of $\mathcal{N}\mathcal{P}$-Hard problems, since is subsumes the complexity that a random graph is connected. In this paper, the computational complexity of DCR-subproblems is discussed in terms of the number of terminal nodes $k=\mathrm{\mid }K\mathrm{\mid }$ and diameter $d$. Either when $d=1$ or when $d=2$ and $k$ is fixed, the DCR is inside the class $\mathcal{P}$ of polynomial-time problems. The DCR turns $\mathcal{N}\mathcal{P}$-Hard when $k\ge 2$ is a fixed input parameter and $d\ge 3$. The case where $k=n$ and $d\ge 2$ is fixed are not studied in prior literature. Here, the $\mathcal{N}\mathcal{P}$-Hardness of this case is established.