2023/07/12 by Noga Alon, Alon, Noga, Allan Grønlund +5 · 1 voice · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems #cs.DS
paper · pdf · doi:10.48550/arxiv.2307.06113
arxiv published 2023/07/12 · arxiv updated 2023/07/31
Computing a shortest path between two nodes in an undirected unweighted graph is among the most basic algorithmic tasks. Breadth first search solves this problem in linear time, which is clearly also a lower bound in the worst case. However, several works have shown how to solve this problem in sublinear time in expectation when the input graph is drawn from one of several classes of random graphs. In this work, we extend these results by giving sublinear time shortest path (and short path) algorithms for expander graphs. We thus identify a natural deterministic property of a graph (that is satisfied by typical random regular graphs) which suffices for sublinear time shortest paths. The algorithms are very simple, involving only bidirectional breadth first search and short random walks. We also complement our new algorithms by near-matching lower bounds.