The most fundamental question one can ask about a graph is also one of the most difficult to answer at scale: "Can I get from point A to point B?" This reachability query is the backbone of social network analysis, biological pathway discovery, and knowledge graph reasoning.
As Chao Zhang, Angela Bonifati, and M. Tamer Özsu outline in their comprehensive survey, researchers have spent four decades trying to escape a brutal space-time tradeoff. On one end, you can precompute every possible path (the transitive closure), which allows for instant lookups but requires $O(n^2)$ space—a physical impossibility for web-scale graphs with billions of nodes. On the other end, you can perform a live search (BFS or DFS) every time a query arrives, which uses no extra space but is far too slow for real-time applications.
The modern research direction focuses on Reachability Indexing: creating compact data structures that "compress" the transitive closure into a manageable memory footprint while providing near-instant query responses.
Compressing Connectivity into Labels
The core intuition behind many indexing strategies is to assign "labels" to nodes such that we can determine reachability just by looking at the labels, without traversing the graph edges.
One powerful approach is Interval Labeling. In a tree, you can label each node with a range $[start, end]$ based on a depth-first traversal; a node $u$ reaches $v$ if and only if $v$'s interval is contained within $u$'s. For general graphs, Avishek Anand and colleagues introduced FERRARI (Paper), which scales this idea by mixing "exact" and "approximate" intervals. By allowing some uncertainty in the labels and resolving it with a small, bounded search, FERRARI fits massive reachability data into a strict memory budget.
For temporal graphs—where edges have timestamps—the problem becomes even more complex. Huanhuan Wu and James Cheng developed TopChain (Paper), which transforms temporal graphs into Directed Acyclic Graphs (DAGs) and uses a "top-$k$ chain labeling" scheme. This allows the system to answer not just if a path exists, but if it exists within a specific time window, while maintaining linear scalability.
Pruning the Search Space with Geometry
If we cannot precompute everything, we can at least precompute enough to rule out "no" answers instantly. This is the logic behind Geometric Pruning.
In FELINE (Paper), Renê Rodrigues Veloso and Mohammed J Zaki use "Dominance Graph Drawing" to map nodes into a 2D coordinate system. If node A cannot reach node B in this 2D space (based on coordinate dominance), it is mathematically impossible for a path to exist in the actual graph. This allows the system to provide an instant "no" for the vast majority of queries, only falling back to a refined search for the "maybe" cases.
Hybridizing Hubs and Landmarks
Another dominant strategy involves identifying "important" nodes that act as transit hubs. Hub Labeling stores, for every node, the distances to a small set of hubs. A query then becomes a simple intersection of two small sets.
However, Hub Labeling often suffers from massive index sizes. Sabine Storandt proposed Landmark Hub Labeling (LHL) (Paper), a hybrid approach that combines the speed of hubs with the space efficiency of landmarks. By using a constant-time "edge oracle" and aggressive pruning, LHL achieves query speeds 50,000x faster than standard A* search while keeping the memory footprint small enough for large-scale road networks.
Beyond Simple Reachability
Modern research is pushing these indices to handle more than just "A to B" connectivity. In Knowledge Graphs, paths often need to satisfy specific constraints. Hongzhi Wang and Xiaolong Wan introduced LSCR (Paper), which handles queries where paths must satisfy edge-label filters and vertex-neighborhood patterns simultaneously.
Similarly, Dimitri Theodoratos and Xiaoying Wu proposed using Summary Graphs as compact materialized views (Paper). Instead of storing a flat list of results, they represent query results as a search space, allowing for hybrid queries that combine direct relationships with complex reachability constraints.
The ultimate goal of this field is to reach "truly subquadratic" performance. As Hung Le and Timothy M. Chan demonstrate in their recent work on geometric graphs, by moving away from traditional graph separators and toward VC-dimension-based data structures, we are finally finding ways to break the $O(n^2)$ barrier for increasingly complex graph types.