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

Heng Guo; Mark Jerrum

doi:10.4230/LIPIcs.ICALP.2018.68

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

Heng Guo, Mark Jerrum

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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.

Original language	English
Title of host publication	45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Editors	Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, Donald Sannella
Place of Publication	Dagstuhl, Germany
Publisher	Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages	68:1-68:12
Number of pages	12
Volume	107
ISBN (Print)	978-3-95977-076-7
DOIs	https://doi.org/10.4230/LIPIcs.ICALP.2018.68
Publication status	Published - 9 Jul 2018
Event	45th International Colloquium on Automata, Languages, and Programming - Prague, Czech Republic Duration: 9 Jul 2018 → 13 Jul 2018 https://iuuk.mff.cuni.cz/~icalp2018/

Publication series

Name	Leibniz International Proceedings in Informatics (LIPIcs)
Publisher	Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume	107
ISSN (Electronic)	1868-8969

Conference

Conference	45th International Colloquium on Automata, Languages, and Programming
Abbreviated title	ICALP 2018
Country	Czech Republic
City	Prague
Period	9/07/18 → 13/07/18
Internet address	https://iuuk.mff.cuni.cz/~icalp2018/

Keywords

Approximate counting
Network Reliability
Sampling
Markov chains

Access to Document

10.4230/LIPIcs.ICALP.2018.68Licence: Creative Commons: Attribution (CC-BY)

A Polynomial-Time Approximation_ICALP_GUO_DoA150418_VoR_CC-BY
© Heng Guo and Mark Jerrum; licensed under Creative Commons License CC-BY
Final published version, 505 KBLicence: Creative Commons: Attribution (CC-BY)

http://drops.dagstuhl.de/opus/volltexte/2018/9072Licence: Creative Commons: Attribution (CC-BY)

Fingerprint Dive into the research topics of 'A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability'. Together they form a unique fingerprint.

1 Article

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
Guo, H. & Jerrum, M., 9 May 2019, In: SIAM Journal on Computing. 48, 3, p. 964–978 15 p.
Research output: Contribution to journal › Article › peer-review

Open Access
File

Cite this

Guo, H., & Jerrum, M. (2018). A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In I. Chatzigiannakis, C. Kaklamanis, D. Marx, & D. Sannella (Eds.), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) (Vol. 107, pp. 68:1-68:12). (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 107). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. https://doi.org/10.4230/LIPIcs.ICALP.2018.68

Guo, Heng ; Jerrum, Mark. / A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). editor / Ioannis Chatzigiannakis ; Christos Kaklamanis ; Dániel Marx ; Donald Sannella. Vol. 107 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2018. pp. 68:1-68:12 (Leibniz International Proceedings in Informatics (LIPIcs)).

@inproceedings{c2b4e5cc20224b129ab542c55f8f0d51,

title = "A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability",

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.",

keywords = "Approximate counting, Network Reliability, Sampling, Markov chains",

author = "Heng Guo and Mark Jerrum",

year = "2018",

month = jul,

day = "9",

doi = "10.4230/LIPIcs.ICALP.2018.68",

language = "English",

isbn = "978-3-95977-076-7",

volume = "107",

series = "Leibniz International Proceedings in Informatics (LIPIcs)",

publisher = "Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany",

pages = "68:1--68:12",

editor = "Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella",

booktitle = "45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)",

note = "45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 ; Conference date: 09-07-2018 Through 13-07-2018",

url = "https://iuuk.mff.cuni.cz/~icalp2018/",

}

Guo, H & Jerrum, M 2018, A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. in I Chatzigiannakis, C Kaklamanis, D Marx & D Sannella (eds), 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). vol. 107, Leibniz International Proceedings in Informatics (LIPIcs), vol. 107, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, Dagstuhl, Germany, pp. 68:1-68:12, 45th International Colloquium on Automata, Languages, and Programming, Prague, Czech Republic, 9/07/18. https://doi.org/10.4230/LIPIcs.ICALP.2018.68

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. / Guo, Heng; Jerrum, Mark.

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). ed. / Ioannis Chatzigiannakis; Christos Kaklamanis; Dániel Marx; Donald Sannella. Vol. 107 Dagstuhl, Germany : Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany, 2018. p. 68:1-68:12 (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 107).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Guo, Heng

AU - Jerrum, Mark

PY - 2018/7/9

Y1 - 2018/7/9

N2 - 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.

AB - 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.

KW - Approximate counting

KW - Network Reliability

KW - Sampling

KW - Markov chains

U2 - 10.4230/LIPIcs.ICALP.2018.68

DO - 10.4230/LIPIcs.ICALP.2018.68

M3 - Conference contribution

SN - 978-3-95977-076-7

VL - 107

T3 - Leibniz International Proceedings in Informatics (LIPIcs)

SP - 68:1-68:12

BT - 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

A2 - Chatzigiannakis, Ioannis

A2 - Kaklamanis, Christos

A2 - Marx, Dániel

A2 - Sannella, Donald

PB - Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany

CY - Dagstuhl, Germany

T2 - 45th International Colloquium on Automata, Languages, and Programming

Y2 - 9 July 2018 through 13 July 2018

ER -

Guo H, Jerrum M. A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. In Chatzigiannakis I, Kaklamanis C, Marx D, Sannella D, editors, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Vol. 107. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany. 2018. p. 68:1-68:12. (Leibniz International Proceedings in Informatics (LIPIcs)). https://doi.org/10.4230/LIPIcs.ICALP.2018.68