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. • Demonstrates Efficiency of Bidirectional Searches: Highlights how bidirectional breadth-first search significantly accelerates shortest path queries in certain real-world networks. • Establishes Sublinear Running Time Parameters: Proves that certain identified parameters result in sublinear running times for bidirectional breadth-first search in various scenarios, including some optimal conditions. • Validates with Real-World Network Experiments: Empirically tests and confirms the relevance of these parameters in capturing practical running times through experiments on a diverse set of real-world networks.