Personal tools
You are here: Home Events LFCS Seminars-Folder LFCS Seminars LFCS seminar: Mark Jerrum: A polynomial-time approximation algorithm for all-terminal network reliability

LFCS seminar: Mark Jerrum: A polynomial-time approximation algorithm for all-terminal network reliability

— filed under: ,

What
  • LFCS Seminar
  • Upcoming events
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 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)

Document Actions