# 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
# 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).

• Are you asking how to do a one-time precomptutation, so that subsequent queries are fast? If you only have a single query to do, you can't do better than $O(|V|+|E|)$ time -- in the worst case you'll need to look at every node. – D.W. Nov 27 '15 at 20:57
• Basically, yes. I will have to call this function many times on the same graph. I've since discovered this wikipedia page, which is basically what I want (except from a set of nodes instead of a single one, but that seems to be trivial). – Jasmijn Nov 27 '15 at 21:17

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.

• I seem to have found something. If I'm correct, it needs $O(log(l) ( k - N))$ space, where $l$ is the length of the longest path in the graph, $k$ is the total number of edges in the graph and $N$ is the number of nodes, and the precomputation time... probably $O(N * (k - N))$? and it allows you to answer the queries in $O(1)$, but I don't know if it's actually correct. (Also, if it actually has the performance I think it does) – Jasmijn Nov 27 '15 at 21:28
• @Robin, OK. Sounds like your next step is to (a) try to prove your algorithm correct (by trying to find a proof), and (b) try to prove your algorithm incorrect (by looking for counterexamples). If you manage to prove it correct, you can write an answer to your own question. If you try both and aren't able to succeed at either, you might be in a position to ask a new question asking whether that algorithm is correct. – D.W. Nov 27 '15 at 21:43
• I'll try that. In the meanwhile, here is my actual code, for anyone who wants to see it: gist.github.com/gvx/cec8e36048212d08d3ae – Jasmijn Nov 27 '15 at 21:46