Document Open Access Logo

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

Authors Heng Guo , Mark Jerrum

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.68.pdf
  • Filesize: 0.49 MB
  • 12 pages

Document Identifiers

Author Details

Heng Guo
  • School of Informatics, University of Edinburgh, Informatics Forum, Edinburgh, EH8 9AB, United Kingdom.
Mark Jerrum
  • School of Mathematical Sciences, Queen Mary, University of London, Mile End Road, London, E1 4NS, United Kingdom.

Funding

  • Jerrum, Mark: The work described here was supported by the EPSRC research grant EP/N004221/1 "Algorithms that Count".

Cite As Get BibTex

Heng Guo and Mark Jerrum. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 68:1-68:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.68

Abstract

We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is to determine the probability that, in a undirected graph, assuming each edge fails independently, the remaining graph is still connected. Our main contribution is to confirm a conjecture by Gorodezky and Pak (Random Struct. Algorithms, 2014), that the expected running time of the "cluster-popping" algorithm in bi-directed graphs is bounded by a polynomial in the size of the input.

Subject Classification

ACM Subject Classification
  • Theory of computation → Generating random combinatorial structures
Keywords
  • Approximate counting
  • Network Reliability
  • Sampling
  • Markov chains

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Michael O. Ball. Complexity of network reliability computations. Networks, 10(2):153-165, 1980. Google Scholar
  2. Michael O. Ball. Computational complexity of network reliability analysis: An overview. IEEE Trans. Rel., 35(3):230-239, 1986. Google Scholar
  3. Michael O. Ball and J. Scott Provan. Calculating bounds on reachability and connectedness in stochastic networks. Networks, 13(2):253-278, 1983. Google Scholar
  4. Henry Cohn, Robin Pemantle, and James G. Propp. Generating a random sink-free orientation in quadratic time. Electr. J. Comb., 9(1), 2002. Google Scholar
  5. Charles J. Colbourn. The Combinatorics of Network Reliability. Oxford University Press, 1987. Google Scholar
  6. Leslie Ann Goldberg and Mark Jerrum. Inapproximability of the Tutte polynomial. Inf. Comput., 206(7):908-929, 2008. Google Scholar
  7. Leslie Ann Goldberg and Mark Jerrum. The complexity of computing the sign of the Tutte polynomial. SIAM J. Comput., 43(6):1921-1952, 2014. Google Scholar
  8. Igor Gorodezky and Igor Pak. Generalized loop-erased random walks and approximate reachability. Random Struct. Algorithms, 44(2):201-223, 2014. Google Scholar
  9. Heng Guo, Mark Jerrum, and Jingcheng Liu. Uniform sampling through the Lovasz local lemma. In STOC, pages 342-355, 2017. Google Scholar
  10. Jane N. Hagstrom. Computing rooted communication reliability in an almost acyclic digraph. Networks, 21(5):581-593, 1991. Google Scholar
  11. David G. Harris and Aravind Srinivasan. Improved bounds and algorithms for graph cuts and network reliability. In SODA, pages 259-278. SIAM, 2014. Google Scholar
  12. François Jaeger, Dirk L. Vertigan, and Dominic J. A. Welsh. On the computational complexity of the Jones and Tutte polynomials. Math. Proc. Cambridge Philos. Soc., 108(1):35-53, 1990. Google Scholar
  13. Mark Jerrum. On the complexity of evaluating multivariate polynomials. Ph.D. dissertation. Technical Report CST-11-81, Dept. Comput. Sci., Univ. Edinburgh, 1981. Google Scholar
  14. Mark Jerrum and Alistair Sinclair. Polynomial-time approximation algorithms for the Ising model. SIAM J. Comput., 22(5):1087-1116, 1993. Google Scholar
  15. David R. Karger. A randomized fully polynomial time approximation scheme for the all-terminal network reliability problem. SIAM J. Comput., 29(2):492-514, 1999. Google Scholar
  16. David R. Karger. A fast and simple unbiased estimator for network (un)reliability. In FOCS, pages 635-644, 2016. Google Scholar
  17. David R. Karger. Faster (and still pretty simple) unbiased estimators for network (un)reliability. In FOCS, pages 755-766, 2017. Google Scholar
  18. Richard M. Karp and Michael Luby. Monte-Carlo algorithms for the planar multiterminal network reliability problem. J. Complexity, 1(1):45-64, 1985. Google Scholar
  19. Kashyap Babu Rao Kolipaka and Mario Szegedy. Moser and Tardos meet Lovász. In STOC, pages 235-244, 2011. Google Scholar
  20. Robin A. Moser and Gábor Tardos. A constructive proof of the general Lovász Local Lemma. J. ACM, 57(2), 2010. Google Scholar
  21. James G. Oxley. Matroid theory. Oxford University Press, 1992. Google Scholar
  22. J. Scott Provan and Michael O. Ball. The complexity of counting cuts and of computing the probability that a graph is connected. SIAM J. Comput., 12(4):777-788, 1983. Google Scholar
  23. James B. Shearer. On a problem of Spencer. Combinatorica, 5(3):241-245, 1985. Google Scholar
  24. Leslie G. Valiant. The complexity of enumeration and reliability problems. SIAM J. Comput., 8(3):410-421, 1979. Google Scholar
  25. Dirk Vertigan and Dominic J. A. Welsh. The compunational complexity of the Tutte plane: the bipartite case. Comb. Probab. Comput., 1:181-187, 1992. Google Scholar
  26. Dominic J. A. Welsh. Complexity: knots, colourings and counting, volume 186 of London Mathematical Society Lecture Note Series. Cambridge University Press, 1993. Google Scholar
  27. Dominic J. A. Welsh. The Tutte polynomial. Random Struct. Algorithms, 15(3-4):210-228, 1999. Google Scholar
  28. David B. Wilson. Generating random spanning trees more quickly than the cover time. In STOC, pages 296-303, 1996. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact