# 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?