LFCS Semiar: 3 April 2018 - Mark Jerrum

Title: A Polynomial-time Approximation Algorithm for all-terminal Network Reliability

Abstract:

Let G be an undirected graph in which each edge is assigned a failure probability.  Suppose the edges fail independently with the given probabilities.  We are interested in computing the probability that the resulting graph is connected, the so-called all-terminal reliability of G.  As this is an #P-hard problem, computing an exact solution is infeasible.  Karger gave an efficient approximation algorithm, in the sense of FPRAS or Fully Polynomial Randomised Approximation Scheme, for all-terminal unreliability (the probability of the network being disconnected).  However, the existence of an FPRAS for unreliability does not imply an FPRAS for reliability, as the operation of subtracting from 1 does not preserve relative error. I shall present an FPRAS for all-terminal reliability or, equivalently, evaluating the Tutte polynomial T(G;x,y) on the semi-infinite line x = 1 and y ≥ 1.  This is the first good news on approximating the Tutte polynomial of unrestricted graphs for a long time.  The main contribution is to confirm a conjecture by Gorodezky and Pak (Random Structures and Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in so-called bi-directed graphs is bounded by a polynomial in the size of the input.  Surprisingly, the cluster popping algorithm on bi-directed graphs solves a disguised version of the all-terminal reliability problem on undirected graphs, a fact that was known to researchers in network reliability in 1980, but seems to have been forgotten in the meantime. Joint work with Heng Guo (Edinburgh)