Improved bounds and algorithms for graph cuts and network reliability

David G. Harris, Aravind Srinivasan

Introduction

The reliability of a network—defined as the probability that a graph $G$ remains connected when its edges fail independently with a given probability $p$—is a fundamental metric in network science and infrastructure planning. While exactly computing this probability is #P-complete, David Karger (1999) introduced the first Fully Polynomial Randomized Approximation Scheme (FPRAS) to estimate the network's unreliability $U(p)$. Although Karger’s algorithm was a theoretical breakthrough, its proven runtime of $n^{5+o(1)} \epsilon^{-3}$ lagged behind experimental observations, which suggested a performance closer to $O(n^3)$. This paper bridges that gap, providing a rigorous $n^{3+o(1)} \epsilon^{-2}$ runtime through novel graph-theoretic bounds and a sophisticated analysis of stochastic processes.

The Reliability Estimation Problem

In a graph $G = (V, E)$ where each edge $e \in E$ fails with probability $p$, the unreliability $U(p)$ is the probability that the graph becomes disconnected. Karger’s approach relies on the fact that the most likely failure modes are "small cuts"—sets of edges whose removal disconnects the graph. By enumerating these cuts and using Monte Carlo sampling, one can approximate $U(p)$. The bottleneck in the original $n^5$ analysis was the loose bounding of the number of "$\alpha$-cuts" (cuts with weight at most $\alpha$ times the minimum cut weight $c$).

Methodological Innovations

1. Stochastic Trajectory Analysis

The most significant theoretical contribution is the treatment of the Contraction Algorithm as a continuous dynamical system. The Contraction Algorithm works by repeatedly merging randomly selected vertices until only two remain. To analyze its success probability, the authors model the discrete, random steps of the algorithm using differential equations. By tracking how graph parameters evolve along "worst-case trajectories," they prove that the real-world random process remains within tight bounds. This approach uses a "generalized Jensen’s inequality" to bridge the gap between deterministic models and stochastic realities.

2. Simultaneous Tightness and New Graph Parameters

Karger’s original analysis utilized several independent graph-theoretic bounds. However, Harris and Srinivasan observed that these bounds cannot be "simultaneously tight." A graph that maximizes one parameter (e.g., the number of min-cuts) must necessarily have a lower value for another parameter that influences the algorithm's success. The authors introduced a new graph parameter that captures this trade-off, allowing for a much tighter estimation of the cut structure. This insight suggests that the reliability of a graph itself limits the number of vulnerable spots it can possess.

3. Structural Bounds for Odd Min-Cuts

The paper provides a refined analysis for graphs where the minimum cut size $c$ is odd. Building on results by Bixby (1974), the authors show that the number of small cuts in such graphs is significantly lower than in graphs with even min-cuts (where a simple cycle represents the worst case). Specifically, they prove there are at most $O(n^{2\alpha \frac{c}{c+1}})$ $\alpha$-cuts, providing a tighter bound than the standard $n^{2\alpha}$.

Algorithmic Refinements

Beyond structural bounds, the authors improve the Recursive Contraction Algorithm (RCA). By optimizing the cut-enumeration process, they reduce the runtime for finding all $\alpha$-cuts from $O(n^{2\alpha} \log^2 n)$ to $O(n^{2\alpha} \log n)$. Furthermore, they replace a generic estimation procedure with a specialized one that exploits the specific structure of graph cuts, significantly reducing the complexity of the statistical sampling phase needed to aggregate failure probabilities.

Results and Discussion

The primary result is a new algorithm that estimates $U(p)$ within a relative error $\epsilon$ in $n^{3+o(1)} \epsilon^{-2}$ time. This result rigorously proves the experimental observations made by Karger and Tai in 1997, which had lacked a formal theoretical basis for decades.

While this paper focuses on unreliability $U(p)$, estimating the reliability $R(p) = 1 - U(p)$ to within a small relative error remains an open challenge when the graph is highly likely to fail. Additionally, the authors note that their "stochastic trajectory" method—using differential equations to bound randomized algorithms—has broad potential for application in other areas of theoretical computer science beyond graph theory.

Summary updated

Abstract

Karger (SIAM Journal on Computing, 1999) developed the first fully-polynomial approximation scheme to estimate the probability that a graph $G$ becomes disconnected, given that its edges are removed independently with probability $p$. This algorithm runs in $n^{5+o(1)} \epsilon^{-3}$ time to obtain an estimate within relative error $\epsilon$. We improve this run-time through algorithmic and graph-theoretic advances. First, there is a certain key sub-problem encountered by Karger, for which a generic estimation procedure is employed, we show that this has a special structure for which a much more efficient algorithm can be used. Second, we show better bounds on the number of edge cuts which are likely to fail. Here, Karger's analysis uses a variety of bounds for various graph parameters, we show that these bounds cannot be simultaneously tight. We describe a new graph parameter, which simultaneously influences all the bounds used by Karger, and obtain much tighter estimates of the cut structure of $G$. These techniques allow us to improve the runtime to $n^{3+o(1)} \epsilon^{-2}$, our results also rigorously prove certain experimental observations of Karger & Tai (Proc. ACM-SIAM Symposium on Discrete Algorithms, 1997). Our rigorous proofs are motivated by certain non-rigorous differential-equation approximations which, however, provably track the worst-case trajectories of the relevant parameters. A key driver of Karger's approach (and other cut-related results) is a bound on the number of small cuts: we improve these estimates when the min-cut size is "small" and odd, augmenting, in part, a result of Bixby (Bulletin of the AMS, 1974).
BibTeX
@inproceedings{harris2014improved,
  author = {David G. Harris and Aravind Srinivasan},
  title = {{Improved bounds and algorithms for graph cuts and network reliability}},
  booktitle = {Random Struct. Algorithms},
  year = {2014},
  doi = {10.1137/1.9781611973402.19},
}
Figure