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$.
Best Answer
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.