Deterministic performance guarantees for bidirectional BFS on real-world networks

A common speedup technique for shortest path queries in graphs is bidirectional search, i.e., performing a forward search from the start and a backward search from the destination until a common vertex is found. In practice, this leads to massive performance improvements on some real-world networks, while saving only a constant factor on other networks. So far, only few studies have attempted to explain the apparent asymptotic speedups on some networks using average-case analysis on certain models of real-world networks. In this paper we provide a new perspective on this, by analyzing deterministic properties that allow theoretical analysis while being easily checked on any particular instance. We prove that these parameters imply sublinear running time for bidirectional BFS in several regimes, some of which are tight. Furthermore, we perform experiments on a large set of real-world networks and show that our parameters capture the concept of practical running time well.