Fork512Hz's blog

Answering queries on if a path exists for DAG in O(1): Preprocessing space complexity optimization?
By Fork512Hz, history, 8 months ago, In English

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.

UPD: There seems to be some paper on this: Paper

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

trick 1 from this blog

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this only reduced the constant factor, instead of the complexity

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      It reduces the time complexity from $$$O(n^2)$$$ to $$$O(n^2/ \log{n})$$$ and memory from $$$O(n^2/ \log{n})$$$ to $$$O(n)$$$.

      If you want to reduce the time complexity even further, consider getting treatment to increase your IQ and invent a way yourself.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Well, reducing from bitset<V> to long long[V/64] does not necessarily cut the space cost by an order of complexity.

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          Did you even read the blog?

          Stop asking questions if you do not want to listen to the answers.

          If you read the blog and do not understand why the space taken is only $$$O(n \log{n} / \log{n}) = O(n)$$$, then you are probably too weak to understand this technique right now, try again later.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It depends of the architecture of the computer, so we can't talk about a real Time Complexity Analysis.

            → Reply
»
8 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I mean we can use optimized Disjoint Set Union? For every edge, do union_sets(u, v).

Now when given a query, check if find_set(u) == find_set(v)? This will achieve almost O(1) time complexity for each query and O(n) space complexity. Learn more about TC here.

Edit:

I noticed that you were asking for DAG, this approach would work for undirected graph.

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Compress graph to DAG first

Now store N bitsets, with bits representing reachable nodes from u. Now for each u simply do dp[u] |= dp[v]. Which will have O(n^2/32) both time and space complexity, but in practice it'll work extremely fast for even N <= 10^5 and sometimes even 2*10^5, depending on constraints and compiller. Common practice is to use pragma (target "popcount" if I remember correctly). Iirc you can't do it any better unless graph has some special structure

→ Reply