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

Abstract

Let $G=(V,E)$ be a simple graph with $|V|=n$ nodes and $|E|=m$ links, a subset $K\subseteq V$ of \emph{terminals}, a vector $p=(p_1,\dots ,p_m)\in [0,1{]}^m$ and a positive integer $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{NP}$-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=|K|$ 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{NP}$-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{NP}$-Hardness of this case is established.

9 pages, 3 figures

Cited by in corpus (1)

• Irrelevant Components and Exact Computation of the Diameter Constrained Reliability