Computational Complexity of Network Reliability Analysis: An Overview

TLDR

Network reliability analysis problems involve determining reliability measures for stochastic networks. The paper provides an overview of computational complexity results for network reliability analysis and discusses their implications for problem‑solving strategies. The authors relate network reliability problems to classic computational network problems such as subnetwork recognition, optimization, and counting. They demonstrate that k‑terminal, 2‑terminal, and all‑terminal network reliability problems are NP‑complete, highlighting the need for careful problem‑solving approaches.

Abstract

This paper presents an overview of results related to the computational complexity of network reliability analysis problems. Network reliability analysis problems deal with the determination of reliability measures for stochastic networks. We show how these problems are related to the more familiar computational network problems of recognizing certain subnetworks, finding optimal subnetworks, and counting certain subnetworks. We use these relationships to show that the k-terminal, the 2-terminal, and the all-terminal network reliability analysis problems are at least as hard as the renowned set of computationally difficult problems, NP-Complete. Finally, we discuss the impact of these results on how one should approach problem solving in this area.