  A common way to accelerate shortest path algorithms on graphs is the use of a
bidirectional search, which simultaneously explores the graph from the start
and the destination. It has been observed recently that this strategy performs
particularly well on scale-free real-world networks. Such networks typically
have a heterogeneous degree distribution (e.g., a power-law distribution) and
high clustering (i.e., vertices with a common neighbor are likely to be
connected themselves). These two properties can be obtained by assuming an
underlying hyperbolic geometry.
  To explain the observed behavior of the bidirectional search, we analyze its
running time on hyperbolic random graphs and prove that it is $\mathcal {\tilde
O}(n^{2 - 1/\alpha} + n^{1/(2\alpha)} + \delta_{\max})$ with high probability,
where $\alpha \in (0.5, 1)$ controls the power-law exponent of the degree
distribution, and $\delta_{\max}$ is the maximum degree. This bound is
sublinear, improving the obvious worst-case linear bound. Although our analysis
depends on the underlying geometry, the algorithm itself is oblivious to it.
