Distance between two vertices picked at random from random graph.

Question

Given random undirected and unweighted graph $G = \langle V, E\rangle$ and random queries consiting of picking two vertices $u, v$ at random how to find the shortest path from $u$ to $v$? Is there anything special in this setting that makes it possible to solve it faster than $O(V(V + E))$ (precomputing all pairs shortest distances with BFS)? By random graph, I mean a graph where every edge has equal probability of being present in a graph. There are some questions at math.se that might seem similar, but they are not.

Answer 1

You can give a probabilistic argument that given any two vertices in the random graph, they almost surely have a common neighbor and hence almost surely the distance between them is less than 2.

To proceed with the proof, we are given $v_1$ and $v_2$ and the parameter $p$ of the random graph $G$ where $p$ is the probability with which an edge between two vertices exists.

Now look at $\{v_1, v_i\}$ and $\{v_2, v_i\}$ for $i = 3, 4, ..., n$. The probability that both of these edges exist is $p^2$, and the probability that there is no such pair of edges $$\left(\{v_1, v_i\}, \{v_2, v_i\}\right)$$ in the graph is $(1 - p^2)^{n - 2}$ which vanishes as $n \to \infty$, or alternately probability that there is at least one such pair is $1 - (1 - p^2)^{n - 2}$ which becomes 1 as $n \to \infty$.

This completes the probabilistic proof that in a random graph G, given any two vertices $v_1, v_2$ they almost surely have a distance of less than or equal to 2.