Reference request: Depth- (or Breadth-) first search with hints? Consider the standard s-t reachability problem of finding a path between nodes $s$ and $t$ in a directed graph $G$. A DFS or BFS could solve it.

Would it be possible to pre-process the graph and compute some "hints" among all nodes in the graph, such that given any node pair $s$ and $t$, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between $s$ and $t$? Therefore, the DFS or BFS will only traverse the "promising" edges to find the $s$-$t$ path. Is it a known problem?

Transitive closure could be one possible "hint". I am wondering if there is any cheaper solution, preferably in O(n) time.

Edits: "promising" means very likely. It appears that it's difficult to compute definitive promising edges (i.e., the edges will definitely be in an $s$-$t$ path). However, will it be possible to compute the promising edges by allowing some reasonable error?
The Reachability Wikipedia page lists several solutions, although the only one which works for general graphs involves computing the transitive closure, which it sounds like you want to avoid.
This is additionally for exact computations of the path.