Obtaining Sets of Ancestors Quickly in a Directed Acyclic Graphs
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 &quot;combinatorial&quot; 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 &lt; 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