A lower bound of the expected maximum number of edge-disjoint s-t paths on probabilistic graphs

For a probabilistic graph , where G is an undirected graph with specified source vertex s and sink vertex t (st) in which each edge has independent failure probability and each vertex is assumed to be failure-free, and is a vector consisting of failure probabilities 's of all edges 's in E, the authors consider the problem of computing the expected maximum number of edge-disjoint s-t paths. It is known that this computing problem is NP-hard even if G is restricted to several classes like planar graphs, s-t out-in bitrees and s-t complete multi-stage graphs. In this paper, for a probabilsitic graph , the authors propose a lower bound of and show the necessary and sufficient conditions by which the lower bound coincides with . Furthermore, they also give a method of computing the lower bound of for a probabilistic graph .