Abstract
As engineered systems expand, become more interdependent, and operate in real-time, reliability assessment is indispensable to support investment and decision making. However, network reliability problems are known to be #P-complete, a computational complexity class largely believed to be intractable. The computational intractability of network reliability motivates our quest for reliable approximations. Based on their theoretical foundations, available methods can be grouped as follows: (i) exact or bounds, (ii) guarantee-less sampling, and (iii) probably approximately correct (PAC). Group (i) is well regarded due to its useful byproducts, but it does not scale in practice. Group (ii) scales well and verifies desirable properties, such as the bounded relative error, but it lacks error guarantees. Group (iii) is of great interest when precision and scalability are required, as it harbors computationally feasible approximation schemes with PAC-guarantees. We give a comprehensive review of classical methods before introducing modern techniques and our developments. We introduce K-RelNet, an extended counting-based estimation method that delivers PAC-guarantees for the K-terminal reliability problem. Then, we test methods' performance using various benchmark systems. We highlight the range of application of algorithms and provide the foundation for future resilience engineering as it increasingly necessitates methods for uncertainty quantification in complex systems.
Introduction: The Challenge of Network Reliability
In infrastructure engineering—spanning power grids, water distribution, and transportation—it is critical to quantify the probability that a network will remain functional despite component failures. This is the core of the network reliability problem. Specifically, this research focuses on $K$-terminal reliability: the probability that a specific subset of nodes ($K$) remains connected.
From a computational standpoint, this problem is #P-complete. This classification suggests that finding exact solutions for large-scale networks in polynomial time is likely impossible. Traditionally, engineers have faced a binary choice: utilize exact methods that fail beyond a few dozen nodes, or rely on guarantee-less sampling (like standard Monte Carlo) that provides no rigorous bounds on the estimate's error. This paper bridges that gap by seeking an $(\epsilon, \delta)$ approximation—an estimate guaranteed to be within a relative error $\epsilon$ with a confidence level of $1-\delta$.
The $\mathcal{K}$-RelNet Framework
The primary contribution of this work is $\mathcal{K}$-RelNet, an efficient approximation algorithm that provides rigorous "Probably Approximately Correct" (PAC) guarantees. The core innovation lies in reducing network reliability to a Projected Model Counting (#$\exists$SAT) problem. The process involves three fundamental steps:
- Weighted-to-Unweighted Transformation: Because edges in real networks have varying failure probabilities, the algorithm employs a mathematical transformation. It converts a graph with arbitrary probabilities into a larger "unweighted" graph where every edge fails with a probability of exactly 0.5. This expansion allows the problem to be treated as a counting problem over binary states.
- Logical Encoding: The "unsafe" state of the network (where the $K$ terminals are disconnected) is encoded as a Boolean formula in Conjunctive Normal Form (CNF). Auxiliary variables are introduced to represent the connectivity state of individual nodes.
- Approximate Counting: The resulting formula is processed by ApproxMC2, a state-of-the-art hashing-based counter. By using a SAT solver as an "NP-oracle," the tool estimates the number of satisfying assignments (failed states), which directly yields the network's unreliability.
Experimental Evaluation
The authors evaluated $\mathcal{K}$-RelNet against two distinct benchmarks:
- Rectangular Grid Networks ($N \times N$): These are used to test scalability. Grids are notoriously difficult for reliability algorithms because they lack simple series-parallel reductions.
- U.S. Power Transmission Networks: A dataset of 58 real-world topologies. These engineered systems often possess structural properties, such as lower treewidth, that differ significantly from random graphs.
Key results indicate that $\mathcal{K}$-RelNet is the first algorithm to provide PAC guarantees for the general $K$-terminal problem. While exact Binary Decision Diagram (BDD) methods failed due to memory limits on larger grids, $\mathcal{K}$-RelNet continued to provide estimates. Furthermore, the algorithm's actual performance often exceeded its theoretical bounds, with observed errors frequently nearing zero even when the allowed $\epsilon$ was large.
Insights and Future Directions
The research highlights a fundamental "Logic-Reliability Bridge." By expressing connectivity as Boolean constraints, reliability analysis can leverage decades of progress in SAT solver technology. However, a "rare-event bottleneck" remains: when edge failure probabilities are extremely small (e.g., $10^{-6}$), the binary representation requires many bits, leading to a variable explosion in the SAT formula.
Future work will focus on more efficient logical encodings to reduce this computational burden. Additionally, because the method is SAT-based, it is uniquely positioned to benefit from future advancements in quantum SAT solvers, potentially offering a path toward even more complex resilience engineering assessments.
Summary updated