Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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'$?

share|improve this question
    
This looks hopeless to have a nice formula isn't it ? –  camomille Mar 20 '11 at 14:39
2  
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
add comment

1 Answer

up vote 1 down vote accepted

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)$.

Although explicit computation won't be feasible for large graphs, under appropriate conditions this might be used to get asymptotics.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.