Skip to main content
Theoretical Computer Science

Return to Question

Bumped by Community user
Bumped by Community user
added 262 characters in body
Source Link
wei wang
wei wang
  • 519
  • 2
  • 7

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?

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.

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?

Source Link
wei wang
wei wang
  • 519
  • 2
  • 7

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.