ALCOMFT-TR-03-193

Thomas Wolle
A Framework for Network Reliability Problems on Graphs of Bounded Treewidth
Utrecht. Work package 2. December 2003.

Abstract: In this paper, we consider problems related to the network reliability problem restricted to graphs of bounded treewidth. We consider undirected simple graphs with a rational number in [0,1] associated to each vertex and edge. These graphs model networks in which sites and links can fail with a given probability, independently of whether other computers or links fail. The number in [0,1] associated to each element is the probability that this element does not fail. In addition, there are distinguished sets of vertices: a set S of servers, and a set L of clients.

This paper presents a dynamic programming framework for graphs of bounded treewidth. For a large number of different properties Y, we can compute with this framework the probability that Y holds in the graph formed by the nodes and edges that did not fail. For instance, it is shown that one can compute in linear time the probability that all clients are connected to at least one server, assuming the treewidth of the input graph is bounded. The classical L-terminal reliability problem can be solved in linear time for graphs of bounded treewidth as well using this framework. The method is applicable to a large number of related questions. Depending on the particular problem, the algorithm obtained by the method uses linear, polynomial, or exponential time.

Postscript file: ALCOMFT-TR-03-193.ps.gz (161 kb).