Check if a path exists between two vertices in a directed acyclic graph - queries

Question

This question can be easily resolved in O (n + m) for each request, but is it possible to answer such requests with greater complexity with preprocessing better than O (n²)?

In the tree, this can easily be done by working with pre-order and in order. I tried something like this in a DAG, but that makes no sense.

I also tried to change this problem to LCA in the DAG task, but finding the LCA in the DAG cannot be resolved quickly enough.

---

To be precise with restrictions, let's say:

n - number of vertices, up to 10 ^ 5

m - number of edges, up to 10 ^ 5

q - the number of requests, up to 10 ^ 5

Answer 1

Interest Ask. My intuition says no. I did not think about it, though.

However (if this question is not theoretical), for practical purposes you can use the Bloom filter .

One possible solution to your problem using the Bloom filter is to first generate K different orders of the graph, and for each, keep the mapping from node to its index in that order. Then, to check the “reachability” from N1 to N2, you check (foreach order) if index-N1 is less than index-N2 (this check is O (1)). If this is true for all orders, this is achieved with a fairly good probability ( provided that K is large enough ). (Depending on your use case in the real world, it may even be ok to tolerate such false positives, or you can run a robust O (N + M) check). Otherwise, this is definitely not the case.

Answer 2

I have a feeling that there may be a solution on the following lines, but this is far from a complete solution.

Let S be a subset of vertices. For each vertex V in the graph, consider the set D_S (V), which I define as follows: D_S (V) = {V} if V is in S, and otherwise D_S (V) is the union of {V} with the set D_S ( W) for all direct descendants of W from V. (That is, it is “all possible descendants of V, but stop the recursion every time you click on the element V”.) The question is, can we find a collection S such that size S is equal to O (f (N)), and also D_S (V) has size O (g (N)) for all V, and where f and g are asymptotically sublinear? (Maybe we can achieve sqrt for both, for example.)

If we can find this, I propose the following strategy. For preprocessing, create a hash table for each U in S containing all the vertices that are ultimately accessible from U. This can be achieved in O (f (N) * M); which is not necessarily better than O (N ^ 2), but better than O (M * Q), at least.

Now, to answer the query “is it accessible from V?”, It is trivial if V is in S. Otherwise, we check if V = U, and in this case it is also trivial. Finally, we apply the same process to all descendants of V, recursively, returning “yes” if the answer “yes” through one of two cases is higher, but “no” only if we never find U. This recursion takes O (g (N)).

The question remains how to choose S. I think that if a graph arises from some process where the external degree follows the power law, you can simply take the vertices sqrt (N) with the highest degree. But, for example, if we have a graph with N = 2 * K vertices (i, 0) and (i, 1), with K ^ 2 edges: from each (i, 0) to each (j, 1); then there is no suitable subset of S. But maybe graphs that do not have a suitable S need some degree of homogeneity, which we can use ... Or maybe not. I dont know. Any ideas let me know!