# Probability of preserving connectivity between pair of vertices in weighted graph

Let $G=(V,E)$ be an undirected graph and $p \colon E \mapsto (0,1]$ defines weights of its edges.

Let's fix two connected vertices $v_1, v_2 \in V$.

Random graph $G'=(V,E')$ is obtained from $G$ by removing each edge $e \in E$ with probability $1-p(e)$.

What is the probability that connectivity between $v_1$ and $v_2$ is preserved in $G'$?

• This looks hopeless to have a nice formula isn't it ? – camomille Mar 20 '11 at 14:39
• You definitely must tell more about the graph (and about the weight function) to get any answer at all. Compare the case of the line graph with $v_1$ and $v_2$ far apart to the case of the complete graph on $n$ vertices with $n$ large. – Did Mar 20 '11 at 14:52
• @Didier well, you right, that's implied part of the question -- if there are no nice results for arbitrary graph, maybe there are any non-trivial classes of graphs, where this problem is trackable? In my context it would be randomly generated scale-free network with number of edges that makes the brute force method unfeasible. – alyst Mar 20 '11 at 17:33

Let L be the set of all simple paths in G from $v_1$ to $v_2$. By inclusion-exclusion, the probability that $v_1$ and $v_2$ are connected is
$\sum_{A \subseteq L} (-1)^{|A|-1} P(\cup A \subseteq E')$
where for any set S of edges, $P(S \subseteq E') = \prod_{e \in S} p(e)$.
• Thanks, Robert. That gives an idea for an alternative formula: if $M$ is a collection of all minimal sets of edges, which removal disrupts connectivity between $v_1$ and $v_2$, then $1 - \sum_{B \subseteq M} (-1)^{|B|-1} P(\cup B \not\subseteq E')$ should also be the sought probability, where $P(S \not\subseteq E') = \prod_{e \in S} (1-p(e))$. – alyst Mar 20 '11 at 21:28