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

Let \((G, p)\) be a probabilistic graph \((G= (V, E, s, t),p)\), where \(G\) is an undirected graph with specified source vertex \(s\) and sink vertex \(t\) \((s\neq t)\) in which each edge has independent failure probability and each vertex is assumed to be failure-free, and \(p= (p(e_ 1),\dots, p(e_{| E|}))\) is a vector consisting of failure probabilities \(p(e_ i)\) of all edges \(e_ i\) in \(E\). The problem of computing the expected maximum number \(\Gamma_{(G, p)}\) of edge-disjoint \(s\)--\(t\) paths in \((G, p)\) is NP-hard. In this paper, the authors give a lower bound for \(\Gamma_{(G, p)}\) and show the necessary and sufficient conditions when this lower bound coincides with \(\Gamma_{(G, p)}\). They also give a method for computing this lower bound for any probabilistic graph \((G= (V, E, s, t), p)\).