Theoretical Computer Science Asked by wei wang on November 16, 2020

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.

Answered by Mark on November 16, 2020

Get help from others!

Recent Answers

- Peter Machado on Why fry rice before boiling?
- haakon.io on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- Jon Church on Why fry rice before boiling?

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP