8
$\begingroup$

1) Is there a better algorithm than the naive O(|E|.|V|) to compute the number of descendants of each vertex in a DAG?

2) Is there an online algorithm to do so, assuming that nodes are added one by one and connect to a non empty subset of the existing nodes?

Context: I'm interested in the case where m = O(n), millions of vertices, tens of millions of edges typically. Alternatively, counting the number of descendants which are also sinks would be useful.

A probabilistic approach would be min-hashing, as a way to represent the set of descendants of every node. The union of the min-hash structure is trivial, and the cardinality of the union can be estimated from the number of coincidences in the min-hashes.

However, I'm not sure how well behaved that would be when propagating up the DAG, intuitively it looks like errors would compound pretty fast.

Very related: https://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag And actually a duplicate of: https://cstheory.stackexchange.com/questions/18787/what-is-the-fastest-deterministic-algorithm-for-incremental-dag-reachability

Improve this question
$\endgroup$
9
  • $\begingroup$ You changed your question. Would O(n^2 + m) for scenario 1 help you? $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 17:55
  • $\begingroup$ It wouldn't be fast enough but I'd be interested in hearing how you do it. $\endgroup$
    – Arthur B
    Apr 4, 2014 at 18:00
  • $\begingroup$ Is the outdegree of your nodes bounded? Or generally, do you have some property of the graph that could help design a faster algorithm? Intuitively a DAG is not simpler as a general graph here, because you can decompose a general graphs into SCCs which form a DAG $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 18:15
  • 1
    $\begingroup$ My apologies for my previous answer - that was definitely wrong! $\endgroup$
    – templatetypedef
    Apr 4, 2014 at 18:22
  • 2
    $\begingroup$ I would suggest you asking this on CS.stackexchange.com. My intuition is that it's a harder problem than it looks like. If you generalize it to the problem where you have node weights and want to know for every node the total reachable weight, it's at least as hard as the same problem for general graphs by the SCC reduction I mentioned. But there might be some techniques to speed up the computation for the type of graphs you are facing $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 18:34

2 Answers 2

Reset to default
5
$\begingroup$
  1. Topologically sort the nodes in your DAG.
  2. For each node N, set N.QueryCount = 0.
  3. For each node N, in reverse topological order:
    • Set N.Descendants = {N} U {C.Descendants | C in N.Children}.
    • Yield (N, N.Descendants.Count) from the algorithm.
    • If N.Parents is empty, you can dispose of N.Descendants.
    • For each C in N.Children, increment C.QueryCount. If C.QueryCount == C.Parents.Count, you can dispose of C.Descendants.

This of course is expensive if your node degrees are large. Worst case complexity may not be significantly better than your unspecified "naive algorithm."

The issue is that this is a very difficult problem to solve. Suppose there is a DAG with millions of nodes, millions of edges, etc. I show you this portion of the graph:

A--> B
 \-> C

How many descendants does A have? The number of descendants of B plus the number of descendants of C minus the number of common descendants of B and C. It's the third term that creates the difficulty. You can't know just the number of descendants of B and C - you need to also know what the descendants are.

Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ That seems to be O(n*m) at least $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 18:23
  • 1
    $\begingroup$ And the naive algorithm would just be doing reachability (DFS or BFS) from every node $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 18:24
  • $\begingroup$ @NiklasB. If set union is O(1) then this is O(n + m). Of course, set union is not, but if node degrees are relatively low it should perform well in terms of CPU and RAM use. EDIT: This is not right, please ignore. $\endgroup$
    – Timothy Shields
    Apr 4, 2014 at 18:24
  • 1
    $\begingroup$ I'm not so sure, even if degrees are low it can happen that a lot of vertices have a lot of successors. For an unbalanced binary tree (for example a chain of nodes) it would be O(n^2) unless you use union-by-weight (but I don't think that gives you a lot for the general case) $\endgroup$
    – Niklas B.
    Apr 4, 2014 at 18:25
  • $\begingroup$ @NiklasB. Oh, right, because the Descendants sets will be close to O(n) in size near the end. $\endgroup$
    – Timothy Shields
    Apr 4, 2014 at 18:27
2
$\begingroup$

Listing all the descendants of all vertices can produce output of the size O(n²), for example if the graph is a linear graph then the vertex without incoming edge has n - 1 descendants, the following vertex n - 2 and so on.

This leaves the question if you can determine the number of descendants without enumerating them. I can not give a proof but I am pretty confident the answer is no. Assume a vertex x has children u and v then you have to find the cardinality of the intersection of the sets of descendants of u and v but there is just nothing you know about that set - u and v may not share a single descendant or they may have the same set of descendants.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.