# Find all the cumulative sums in a DAG

Let's call G a DAG (directed acyclic graph) with N nodes labeled with a natural value.

We define the cumulative sum of a node v as the sum of the value of all the ancestor nodes of v (including v).

For example, the cumulative sum of d in the following DAG is 7:

      a (2)
/ \
v   v
(1) b   c (3)
\ /
v
d (1)


Is it posible to compute the cumulative sum for a set of M nodes in G, in less than O(M*(N + E))?

Clarification: computing the cumulative sum for a set of nodes refers to computing the cumulative sum for each node of the set.

Further clarification: for a given cumulative sum, each ancestor is counted only once (notice that the ancestors of $u$ include $u$):

$cumsum(v) = \sum_{u \in \text{ancestors of } v} \text{value of } u$

Which does not imply:

$cumsum(v) = \text{value of } v + \sum_{u \in \text{direct ancestors of } v} cumsum(u)$

because this last formula may count ancestors multiple times. For example, in the diamond example we have:

$cumsum(d) = 7$
$cumsum(b) = 3$
$cumsum(c) = 5$
so $cumsum(d) \neq 1 + cumsum(b) + cumsum(c)$

Solution in O(M*(N + E)):

To compute the cumulative sum of a single node v in O(N + E), sort the DAG topologically and traverse the sorted list of vertices backwards, tainting all ancestors of v with the back edges, and adding the values of all the ancestors. (You could also just do a DFS for the same price).

Doing this for each node in the given set of M nodes gives a running time of O(M*(N + E)).

Although it doesn't affect the final running time, the topological sort could be done only once before looping through each cumulative sum calculation.

• Can you define the cumulative sum of a set of nodes? – D.W. Feb 14 '18 at 0:22
• It refers to computing the cumulative sum multiple times, one for each node in the set – esneider Feb 14 '18 at 0:38
• It would help to edit the question to incorporate that into the question. Anyway, I suggest you spend some more time thinking about the problem. Can you avoid redoing any computation? – D.W. Feb 14 '18 at 0:43
• You should probably include the solution in Tomoki's answer, and explain why it doesn't work. – Yuval Filmus Feb 14 '18 at 16:27
• After reading your comment on Tomoki's now-deleted answer I am now thoroughly confused. Tomoki's answer seems obviously correct to me and I don't understand why you rejected it. Have I misunderstood the goal? Can you specify the problem more clearly? An example is not a substitute for a precise problem specification. It would help to list the desired output, and provide a mathematical definition of what it means for the output to be correct. – D.W. Feb 14 '18 at 20:17