Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs

Question

Suppose I have a DAG, $G = (V, E)$ and we know that all nodes in the DAG have at most $A$ ancestors. Let $V' \subseteq V$ be a subset of vertices of $V$. Is there a way to obtain the set of all ancestors of every vertex in $V'$ in $O(|V'|A + m)$ time? In other words, I want sets $B_i$ consisting of all ancestors of $v_i \in V'$ for all $v_i$.

The trivial algorithm does this in $O(|V'|A^2)$ time (for very dense graphs) but I would like to do this in $O(|V'|A + m)$ time or even better $O(|V'|A + E(V', B(V')))$. (Here $E(V', B(V'))$ indicates time proportional to the induced subgraph consisting of $V'$ and all ancestors of vertices in $V'$.)

If we cannot do this, are there any known lower bounds for this runtime?

Answer 1

We can reduce Boolean matrix multiplication to this problem by a three level construction, where the edges from the first level to the second level are determined by the first matrix and the edges from the second level to the third level are determined by the second matrix, and we query with $V'$ equal to the first level.

This reduction for $n \times n$ matrix produces an instance with $|V'| = n$, $A = O(n)$, and $m = O(n^2)$, so an $O(|V'|A + m)$ time algorithm would imply an $O(n^2)$ time algorithm for Boolean matrix multiplication. While I don't think that this has been conjectured to be impossible, it would be a breakthrough result: Best algorithms for Boolean matrix multiplication have the same time complexity as general matrix multiplication, and no "combinatorial" algorithms with $O(n^{3-\epsilon})$ time complexity are known. (see e.g. the intro of [1] for references).

An algorithm with time complexity $O(|V|^\omega \log(|V|))$, where $2 \le \omega < 2.373$ is the matrix multiplication exponent can be given by computing the transitive closure of the DAG with matrix multiplication.

[1] https://acris.aalto.fi/ws/portalfiles/portal/40881045/1.9781611975482.31.pdf