Answering queries on if a path exists for DAG in O(1): Preprocessing space complexity optimization?

Revision en1, by Fork512Hz, 2024-03-20 08:50:40

Problem:

Given a directed graph and $$$q$$$ queries. For each query, you need to answer whether a path exists from point $$$x$$$ to point $$$y$$$. Each query needs to be processed within $$$O(1)$$$.

A BF solution is, we can do $$$V$$$ DFSs from every vertex and set the bits in the answer matrix for each visited vertex, and the complexity of preprocessing is $$$O(V^2)$$$. You can do some optimizations to reduce the steps taken in the traversal by a lot, but as long as you store the answer in a matrix, $$$O(V^2)$$$ space complexity leads to an inevitable $$$O(V^2)$$$ time complexity.

Now the question is: is it possible to do the preprocessing within less than $$$O(V^2)$$$ time, or at least, less than $$$O(V^2)$$$ space? At least, if queries are to be processed online, it seems highly improbable.

I wrote DAG in the title, because we can run Tarjan's to find out SCCs and if $$$x$$$ and $$$y$$$ belong to the same SCC it's a clear YES.

Tags graph, paths, preprocessing, optimization, question

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Fork512Hz 2024-03-20 10:47:48 88
en1 English Fork512Hz 2024-03-20 08:50:40 1007 Initial revision (published)