Sparse reliable graph backbones

Given a connected graph G and a failure probability p ( e ) for each edge e in G, the reliability of G is the probability that G remains connected when each edge e is removed independently with probability p ( e ). In this paper it is shown that every n-vertex graph contains a sparse backbone, i. e. , a spanning subgraph with O ( n log n ) edges whose reliability is at least ( 1 − n − Ω ( 1 ) ) times that of G. Moreover, for any pair of vertices s, t in G, the ( s, t ) -reliability of the backbone, namely, the probability that s and t remain connected, is also at least ( 1 − n − Ω ( 1 ) ) times that of G. Our proof is based on a polynomial time randomized algorithm for constructing the backbone. In addition, it is shown that the constructed backbone has nearly the same Tutte polynomial as the original graph (in the quarter-plane x ⩾ 1, y > 1 ), and hence the graph and its backbone share many additional features encoded by the Tutte polynomial.

Authors

• Shiri Chechik
• Yuval Emek
• Boaz Patt-Shamir
• David Peleg

Keywords

• Network reliability
• Sparse subgraphs
• Tutte polynomial