Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of undirected path existence between any two vertices $v$ and $u$ in such a graph? In particular I'm interested in relatively efficient algorithm for estimating this probabilities for all pairs of vertices.

This could be seen as transforming each link in this graph into undirected edge and then asking for being in the same connected component.

Although this problem seems to be quite common I could find it's instances only for some particular random graph models which didn't helped me.

I managed to get the probability of directed path existence, probably this could be used somehow, but definitely it's far from the answer since such a chain v -> x <- u is connected in my terms but there is no directed path between $v$ and $u$.

  • 3
    $\begingroup$ You are probably aware that the keyword is "Percolation" --I mention it since you didn't. In Percolation theory it is customary to assume independence (distinct arcs being open are independent events). You are assuming it as well? $\endgroup$ Aug 2 '13 at 10:48
  • $\begingroup$ I'm not sure that I understood you correctly. Do you mean that links are generated independently? If so, then yes, I should mention this in my question $\endgroup$
    – sbos
    Aug 2 '13 at 11:48
  • $\begingroup$ For clarification: Are you interested in the probability of directed path (you wrote undirected in the description)? If you are interested in directed path, I think you need the random graph to be connected, at least with some high probability. In the Erdos-Renyi case, that would mean that you need to have identical (and undirected) $a_{uv} \ge \frac{log N}{N}$. I think you could get, at the very least, good hints about how to do this for non-identical (undirected) $a_{uv}$ by say looking up [win.tue.nl/~rhofstad/NotesRGCN.pdf](R. van der Hofstad's notes on Random Graphs). $\endgroup$ Aug 17 '13 at 6:13

How about the Monte Carlo method? Generate $k\gg 1$ graphs at random, count how many of them have a path from $u$ to $v$, then divide by $k$.

This is about the best polynomial-time approximation known for the general problem, "s-t reliability". In particular it is not known whether there is a fully polynomial randomised approximation scheme. See Rico Zenklusen's PhD dissertation for more information.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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