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