Principled network reliability approximation: A counting-based approach

Roger Paredes, Leonardo Dueñas-Osorio, Kuldeep S. Meel, Moshe Y. VardiReliab. Eng. Syst. Saf 2019 · OpenReview

Abstract

This paper develops a network reliability approximation method with user-specified error and confidence (PAC guarantees). It relies on a counting method and increasingly powerful satisfiability (SAT) solvers. We discuss the results of our method, $\mathcal{K}$-RelNet, relative to several modern competitive techniques and showcase its capabilities using ideal networks and power transmission grids.

Introduction

Quantifying the reliability of critical infrastructure—such as power grids, water systems, and telecommunications—is vital for risk assessment and system design. However, determining the probability that a specific subset of nodes $\mathcal{K}$ remains connected (the $\mathcal{K}$-terminal reliability problem) is computationally "intractable," belonging to the complexity class #P-complete.

Existing approaches generally fall into two camps: exact methods that provide perfect answers but fail to scale, and standard Monte Carlo sampling which scales well but lacks a priori error bounds. In "rare-event" scenarios where systems are highly reliable, sampling requires an astronomical number of samples to achieve precision. This paper introduces $\mathcal{K}$-RelNet, a "principled" middle ground that provides rigorous Probably Approximately Correct (PAC) guarantees.

Methodology

The core innovation of $\mathcal{K}$-RelNet is reducing network reliability to a Boolean model counting problem. This allows the algorithm to leverage the efficiency of modern SAT solvers. The process involves three key steps:

  1. Weighted-to-Unweighted Transformation: Real-world networks have edges with varying failure probabilities. $\mathcal{K}$-RelNet uses a series-parallel graph transformation to convert a "weighted" reliability problem into an "unweighted" one where every edge has a failure probability of exactly 0.5.
Figure 1: Transformation of a weighted network instance (a) into an equivalent unweighted instance (b) where all edge probabilities are 1/2.
  1. Logic Encoding: The "unsafe" state of the network (where nodes in $\mathcal{K}$ are disconnected) is encoded into a Boolean formula in Conjunctive Normal Form (CNF). The authors use projected counting ($\Sigma^1_1$ formulas) to focus the problem on edge variables while using auxiliary variables to represent connectivity.
  2. Approximate Model Counting: The resulting formula is processed by ApproxMC2, a state-of-the-art hashing-based counter. This tool uses a SAT-oracle to estimate the number of satisfying assignments, which directly corresponds to the network's unreliability.

Experimental Evaluation

The authors evaluated $\mathcal{K}$-RelNet using two primary benchmarks:

  • Rectangular Grid Networks: $N \times N$ square grids (up to $100 \times 100$) used to test scalability against varying edge failure probabilities.
  • U.S. Power Transmission Networks: 58 real-world topologies from various U.S. cities, providing a testbed for sparse, "engineered" topologies with low treewidth.

Key Insights and Results

$\mathcal{K}$-RelNet is the first efficient PAC method for the general $\mathcal{K}$-terminal reliability problem. Unlike "guarantee-less" methods relying on the Central Limit Theorem, PAC methods provide provably sound approximations even with a finite number of samples.

Experiments showed that while exact methods (like BDD-based HLL) failed as grid sizes increased due to memory exhaustion, $\mathcal{K}$-RelNet continued to provide estimates for much larger systems. In catastrophic scenarios (higher failure probabilities $\approx 0.1$), $\mathcal{K}$-RelNet is highly competitive. Interestingly, empirical results showed that the theoretical error bounds are often much more conservative than actual performance; the algorithm is frequently more accurate than the math strictly requires.

Limitations and Future Work

A primary bottleneck is the "Small $p$" problem. The weighted-to-unweighted transformation can lead to a "variable explosion" when failure rates are extremely low (e.g., $10^{-6}$). Future work will focus on more efficient logical encodings for highly reliable systems and refining mathematical analysis to provide tighter practical guarantees. Additionally, as a SAT-based approach, $\mathcal{K}$-RelNet is well-positioned to benefit from future breakthroughs in quantum computing hardware.

Conclusion

By treating reliability as a combinatorial counting problem rather than a simulation task, $\mathcal{K}$-RelNet bridges the gap between theoretical rigor and practical scalability. It offers a robust framework for assessing the reliability of complex, large-scale networks with mathematical certainty.

Summary updated

Abstract

Highlights•Develops network reliability approximation with user-specified error and confidence.•Relies on a counting method and increasingly powerful satisfiability (SAT) solvers.•Discusses results of our method relative to several modern competitive techniques.•Showcases our capabilities using ideal networks and power transmission grids.
BibTeX
@inproceedings{paredes2019principled,
  author = {Roger Paredes and Leonardo Dueñas-Osorio and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{Principled network reliability approximation: A counting-based approach}},
  booktitle = {Reliab. Eng. Syst. Saf},
  year = {2019},
  url = {https://openreview.net/forum?id=tNOXxEBXFz},
}
Figure