An O(n×log(n)) algorithm to compute the all-terminal reliability of (K5, K 2.2.2) free networks

A graph is (K₅, K_2.2.2) free if it has no subgraph contractible to K₅ or K_2.2.2. The class of partial 3-trees (also known as Y-Δ graphs) is a proper subset of (K₅, K _2.2.2) free graphs. Let G be a network with perfectly reliable points and edges that fail independently with some known probabilities. The all-terminal reliability R(G) of G is the probability that G is connected. Computing R(G) for a general network is NP-hard. This paper presents an O(n log n) algorithm to compute R(G) of any (K₅, K_2.2.2) free graphs on n points. The running time of this algorithm is O(n) if G is planar