Sublinear Time Shortest Path in Expander Graphs

Noga Alon, Allan Grønlund, Søren Fuglede Jørgensen, Kasper Green Larsen

TL;DR

Shortest path algorithms like BFS typically require linear time, but this paper proves that for expander graphs—graphs that are sparse yet highly connected—we can find shortest paths in sublinear time (roughly $\sqrt{n}$). By using simple bidirectional search and random walks, the authors provide algorithms that work for most or all node pairs and prove that these methods are nearly optimal through new lower bounds.

What Problem Does This Paper Address?

In graph theory, finding the shortest path between two nodes ($s$ and $t$) is a bread-and-butter task. The standard textbook approach, Breadth-First Search (BFS), takes $O(m + n)$ time, where $n$ is the number of nodes and $m$ is the number of edges. In the worst case, you simply have to look at a large portion of the graph.

However, researchers previously noticed that for certain random graphs, you can find paths much faster—in sublinear time—using a "bidirectional BFS" (starting from both $s$ and $t$ until the searches meet). The gap addressed here is theoretical: What is the underlying deterministic property that allows for sublinear shortest paths? The authors identify this property as "expansion" and move beyond the limitations of purely probabilistic graph models.

Methods

The authors analyze two primary algorithmic strategies:

  1. Bidirectional BFS: This involves running two BFS processes simultaneously: one from the source $s$ and one from the target $t$. The algorithm stops as soon as the two "search bubbles" share a common node. The authors prove that in expander graphs, these bubbles expand so rapidly that they are guaranteed to collide very quickly for the vast majority of node pairs.
  2. BFS + Random Walks: To handle the "difficult" pairs of nodes that bidirectional BFS might miss, the authors propose a randomized hybrid. They grow a BFS tree from $s$ to a certain size and then launch multiple short random walks from $t$. Because expanders are "well-mixed," these random walks have a high probability of bumping into the BFS tree from $s$, creating a "short" (though not necessarily "shortest") path.
  3. Query Model for Lower Bounds: To prove their algorithms are efficient, they use a "node-incidence query" model. They show that any algorithm, no matter how clever, must ask at least $\Omega(\sqrt{n})$ queries to find a path in typical expander-like random graphs.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets. Instead, it provides rigorous mathematical proofs for specific classes of graphs:

  • $(n, d, \lambda)$-graphs: Deterministic expander graphs defined by their number of nodes, degree, and spectral gap.
  • Ramanujan Graphs: The "gold standard" of expanders with the best possible spectral gap.
  • Erdős-Rényi and Random $d$-regular graphs: Used specifically to establish lower bounds.

Key Insights and Ideas

  • Expansion is the Key: You don't need a graph to be "random" to get sublinear performance. The deterministic property of having a large spectral gap (meaning the graph has no bottlenecks) is sufficient.
  • The Birthday Paradox at Scale: The reason $\sqrt{n}$ appears is analogous to the Birthday Paradox. In a well-connected graph, two sets of $\sqrt{n}$ nodes are very likely to have an intersection, just as two groups of people are likely to share a birthday.
  • Short vs. Shortest Trade-off: There is a fundamental trade-off discovered. Bidirectional BFS finds the shortest path for most pairs. If you need a path for every pair with high probability, you can get a short path (within a constant factor of the shortest) using random walks.

Key Results

  • For Ramanujan Graphs: Bidirectional BFS finds the shortest path for $(1-\delta)n$ nodes after visiting only $O(\sqrt{n} \cdot \text{polylog } n)$ nodes.
  • Universal Reachability: The BFS + Random Walk algorithm finds a path of length $O(\log n)$ for any pair of nodes in an expander while visiting only $O(\sqrt{n \ln(1/\delta)})$ nodes.
  • Optimality: The authors prove a lower bound of $\Omega(\sqrt{n})$ for random $d$-regular graphs, showing that their $O(\sqrt{n})$ upper bounds are essentially the best one can hope for.

Limitations and Future Work

  • "Most" vs. "All": The most efficient shortest-path result (Theorem 1) only applies to a $(1-\delta)$ fraction of node pairs. Finding the absolute shortest path for every pair in sublinear time remains an open challenge or may be impossible under these constraints.
  • Unweighted Only: The current work focuses on unweighted, undirected graphs. Extending these sublinear results to weighted graphs (where BFS is replaced by Dijkstra-like heuristics) is a natural next step.
  • Random Walk Length: The "short path" algorithm provides a path of length $O(\log n)$. While this is asymptotically optimal for expanders, the constant factors involved in the random walk approach could be optimized.

Summary updated

Abstract

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.
BibTeX
@inproceedings{alon2024sublinear,
  author = {Noga Alon and Allan Grønlund and Søren Fuglede Jørgensen and Kasper Green Larsen},
  title = {{Sublinear Time Shortest Path in Expander Graphs}},
  booktitle = {MFCS},
  year = {2024},
  doi = {10.4230/lipics.mfcs.2024.8},
}
Figure