What is an efficient algorithm to see if a set of nodes ultimately depend on a certain node in a DAG? Hopefully this question makes sense. Basically, given a DAG, a set of nodes A, and another node b, I'd like to know if node b is an ancestor of any of the nodes in A in that graph.

This is my current implementation:

def is_ancestor(graph, A, b):
    nodes_visited = set()
    frontier = list(A)
    while frontier:
        node = frontier.pop()
        if node not in nodes_visited:
            if node == b:
                return False
            nodes_visited.add(node)
            # add immediate predecessors to the frontier
            frontier.extend(graph.predecessors_iter(node))
    return True


However, in the worst case this is O(|graph|), and this would be a function I would need to call very often, so I'm wondering if I'm missing anything that might make this run faster, preferably without requiring quadratic memory, because then I could just store everything and get O(1).
As far as I know, it is an open problem whether one can do significantly better (in an asymptotic sense).

This is known as the reachability query problem for DAGs.  You want to do some precomputation, after which you can answer queries of the form Reachable$(u,v)$ (which should return true if $v$ is reachable via some path from $u$, i.e., if $u$ is an ancestor of $v$).

There are two trivial algorithms:


With no precomputation, you can answer each reachability query in $O(|V|+|E|)$ time by just using DFA.
With a $O(|V| \cdot |E|)$-time precomputation and $O(|V|^2)$ space, you can precompute the transitive closure of the DAG and then answer each query in $O(1)$ time.


Apparently it is an open problem to do significantly better than this: e.g., to precompute something with less than $O(|V|^2)$ space that enables you to answer reachability queries efficiently.  See https://cstheory.stackexchange.com/q/25298/5038 and https://cstheory.stackexchange.com/q/21503/5038.