Karger (STOC 1995) gave the first FPTAS for the network (un)reliability problem, setting in motion research over the next three decades that obtained increasingly faster running times, eventually leading to a $\tilde{O}(n^2)$-time algorithm (Karger, STOC 2020). This represented a natural culmination of this line of work because the algorithmic techniques used can enumerate $\Theta(n^2)$ (near)-minimum cuts. In this paper, we go beyond this quadratic barrier and obtain a faster algorithm for the network unreliability problem. Our algorithm runs in $m^{1+o(1)} + \tilde{O}(n^{1.5})$ time. Our main contribution is a new estimator for network unreliability in very reliable graphs. These graphs are usually the bottleneck for network unreliability since the disconnection event is elusive. Our estimator is obtained by defining an appropriate importance sampling subroutine on a dual spanning tree packing of the graph. To complement this estimator for very reliable graphs, we use recursive contraction for moderately reliable graphs. We show that an interleaving of sparsification and contraction can be used to obtain a better parametrization of the recursive contraction algorithm that yields a faster running time matching the one obtained for the very reliable case.
翻译:----
Karger(STOC 1995)提出了网络(不)可靠性问题的第一个FPTAS,随后的三十年内进行了研究,得到了越来越快的运行时间,最终导致了一个 $\tilde{O}(n^2)$ 时间算法(Karger,STOC 2020)。这代表了这一工作线的自然顶点,因为所使用的算法技术可以列举$\Theta(n^2)$(近似)最小割。在本文中,我们超越了这一二次时间障碍,获得了更快的网络不可靠性算法。我们的算法在$m^{1+o(1)}+\tilde{O}(n^{1.5})$ 时间内运行。我们的主要贡献是一个适用于非常可靠图形的新估计器。由于断开事件很难捕获,这些图形通常是网络不可靠性的瓶颈。我们通过在图形的双重生成树包中定义适当的重要性采样子程序来获得我们的估计器。为了补充非常可靠图形的估计器,我们使用递归收缩来处理中等可靠性图形。我们展示了稀疏化和收缩的交错可以用于获得更好的递归收缩算法的参数化,从而产生与非常可靠情况下所获得的相同的更快速度的运行时间。