LFCS seminar: Mark Jerrum: A polynomialtime approximation algorithm for allterminal network reliability
What 


When 
Apr 03, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
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 socalled allterminal reliability of G. As this is an #Phard 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 allterminal 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 allterminal reliability or, equivalently, evaluating the Tutte polynomial T(G;x,y) on the semiinfinite 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 "clusterpopping" algorithm in socalled bidirected graphs is bounded by a polynomial in the size of the input. Surprisingly, the cluster popping algorithm on bidirected graphs solves a disguised version of the allterminal 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)