0
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ This looks hopeless to have a nice formula isn't it ? $\endgroup$
    – camomille
    Mar 20, 2011 at 14:39
  • 2
    $\begingroup$ 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. $\endgroup$
    – Did
    Mar 20, 2011 at 14:52
  • $\begingroup$ @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. $\endgroup$
    – alyst
    Mar 20, 2011 at 17:33

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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))$. $\endgroup$
    – alyst
    Mar 20, 2011 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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