<p>The <a href="https://en.wikipedia.org/wiki/Reachability" rel="nofollow noreferrer">Reachability</a> 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.</p>

CC BY-SA 4.0
2020-03-29T05:57:40.250Z
2020-03-29T05:57:40.250Z
Mark Schultz-Wu
<p>Consider the standard s-t reachability problem of finding a path between nodes <span class="math-container">$s$</span> and <span class="math-container">$t$</span> in a directed graph <span class="math-container">$G$</span>. A DFS or BFS could solve it.</p>

<p>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 <span class="math-container">$s$</span> and <span class="math-container">$t$</span>, the DFS or BFS procedure knows that some edges are more likely contributing to a path (if any) between <span class="math-container">$s$</span> and <span class="math-container">$t$</span>? Therefore, the DFS or BFS will only traverse the "promising" edges to find the <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path. Is it a known problem?</p>

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

<p>Edits: "promising" means very likely. It appears that it's difficult to compute <em>definitive</em> promising edges (i.e., the edges will definitely be in an <span class="math-container">$s$</span>-<span class="math-container">$t$</span> path). However, will it be possible to compute the promising edges by allowing some reasonable error?</p>

<graph-theory><graph-algorithms>
Reference request: Depth- (or Breadth-) first search with hints?
wei wang
# Reference request: Depth- (or Breadth-) first search with hints?

(Asked by: username_0 on 2020-03-28)

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?

**Tags:** graph-theory, graph-algorithms


---

## 1 answers

### Answer by username_1 on 2020-03-29. Score: 1

The [Reachability](https://en.wikipedia.org/wiki/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.


---

