2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you define the cumulative sum of a set of nodes? $\endgroup$ – D.W. Feb 14 '18 at 0:22
  • $\begingroup$ It refers to computing the cumulative sum multiple times, one for each node in the set $\endgroup$ – esneider Feb 14 '18 at 0:38
  • $\begingroup$ 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? $\endgroup$ – D.W. Feb 14 '18 at 0:43
  • 1
    $\begingroup$ You should probably include the solution in Tomoki's answer, and explain why it doesn't work. $\endgroup$ – Yuval Filmus Feb 14 '18 at 16:27
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 14 '18 at 20:17
1
$\begingroup$

It's possible to do slightly faster, by using sophisticated algorithms for transitive closure based on fast matrix multiplication, but apparently it is not known how to do this much faster than the naive solution. See https://cstheory.stackexchange.com/q/553/5038 and https://cstheory.stackexchange.com/q/736/5038 and https://cstheory.stackexchange.com/q/4258/5038.

$\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.