arXiv:2608.02523 · v2

Approximating two-terminal network reliability

首次提交 2026-08-04 01:18

版本更新 2026-11-04 04:45

雷达观测 2026-11-05 11:11

摘要

We present fully polynomial-time randomised approximation schemes (FPRAS) for the two-terminal reliability problem on general graphs, both directed and undirected. For directed graphs with $n$ vertices and $m$ arcs, the running time is $\widetilde{O}(nm\varepsilon^{-2})$, where $\varepsilon$ is the relative error. For undirected graphs with $n$ vertices and $m$ edges, it runs in $\widetilde{O}(m+n^2\varepsilon^{-2})$. We also show that the complementary unreliability problem is #BIS-hard.

作者备注：v2: faster algorithm, 58 pages