Edge-packings of graphs and network reliability

The reliability of a network can be efficiently bounded using graph-theoretical techniques based on edge-packing. The paper examines the application of combinatorial theorems on edge-packing spanning trees, s, t-paths, and s, t-cuts to the determination of reliability bounds. The application of spanning trees has been studied by Polesskii, and the application of s,t-paths has been studied by Brecht and Colbourn. The use of edge-packings of s,t-cutsets has not been previously examined. The paper compares the resulting bounds with known bounds produced by different techniques, and establishes that the edge-packing bounds often produce a substantial improvement. It also establishes that three other edge-packing problems arising in reliability bounding are NP-complete, namely edge-packing by network cutsets, Steiner trees, and Steiner cutsets.