<p>We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2<sup><i>n</i></sup>.  Then the current task cannot be performed even in a slightly weaker time bound O(<i>n</i><sup>2</sup>), unless the transitive closure of an arbitrary directed graph can be computed in O(<i>n</i><sup>2</sup>) time, where <i>n</i> denotes the number of vertices.  (Note that an O(<i>n</i><sup>2</sup>)-time algorithm for the transitive closure will be a breakthrough.)  This is the contrapositive of the following claim:</p>

<p><strong>Claim</strong>.  If the current task can be performed in time O(<i>n</i><sup>2</sup>), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(<i>n</i><sup>2</sup>) time (assuming some reasonable computational model).</p>

<p><strong>Proof</strong>.  As a preprocessing, we compute the strongly connected component decomposition of the given directed graph <i>G</i> in time O(<i>n</i><sup>2</sup>) to obtain a DAG <i>G</i>′.  Note that if we can compute the transitive closure of <i>G</i>′, we can reconstruct the transitive closure of <i>G</i>.</p>

<p>Now assign the weight 2<sup><i>i</i></sup> to each vertex <i>i</i> of the DAG <i>G</i>′ and use the algorithm for the current problem.  Then the binary representation of the sum assigned to each vertex <i>i</i> describes exactly the set of ancestors of <i>i</i>, in other words, we have computed the transitive closure of <i>G</i>′.  <strong>QED</strong>.</p>

<p>The converse of the claim also holds: if you can compute the transitive closure of a given DAG, it is easy to compute the required sums by additional work in time O(<i>n</i><sup>2</sup>).  Therefore, in theory you can achieve the current task in time O(<i>n</i><sup>2.376</sup>) by using the algorithm for the transitive closure based on the <a href="http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm">Coppersmith-Winograd matrix multiplication algorithm</a>.</p>

<p><em>Edit</em>: Revision 2 and earlier did not state the assumption about the range of vertex weights explicitly.  Per Vognsen pointed out in a comment that this implicit assumption may not be reasonable (thanks!), and I agree.  Even if arbitrary weights are not needed in applications, I guess that this answer might rule out some approaches by the following line of reasoning: “If this approach worked, it would give an algorithm for the arbitrary weights, which is ruled out unless the transitive closure can be computed in time O(<i>n</i><sup>2</sup>).”</p>

<p><em>Edit</em>: Revision 4 and earlier stated the direction of edges incorrectly.</p>

CC BY-SA 2.5
2010-09-29T03:21:31.227Z
I was thinking about this very thing last night since one practical solution uses bit vectors to do the exclusion counting. I guess the only question is whether it's reasonable to assume that the weights can have bit length proportional to n. In practice, I can imagine the weights are bounded by some k so that the maximal possible sum is kn, which isn't enough bits to pull this trick.
Per Vognsen
CC BY-SA 2.5
2010-09-29T04:15:34.847Z
@Per: I agree that the assumption that vertex weights can be n-bit integers might be questionable.  I edited the answer to make this assumption explicit.  Thanks!
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T04:26:22.487Z
@Per: I realized that if the vertex weights are integers bounded by O(1), the problem reduces to [the case where all vertices have weight 1](http://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag) by duplicating vertices in a suitable way.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T04:33:42.297Z
Unfortunately I don't see an answer in that thread to the counting problem. The counts contain logarithmically less information than the listing of the transitive closure, O(n log n) vs O(n^2), so I don't see how a straightforward reduction could work.
Per Vognsen
CC BY-SA 2.5
2010-09-29T04:40:25.463Z
By the way, an interesting version of this problem is when we have a bound on the branch factor and information on the growth in size of the generations (a la topological sort) of the DAG. If the growth is exponential, the pattern is essentially tree-like. What if it's linear, log-linear, quadratic, etc?
Per Vognsen
CC BY-SA 2.5
2010-09-29T14:56:25.277Z
Nice argument!  It perhaps worth noting that the asymptotically best algorithm for transitive closure is via matrix multiplication.  So this is a $O(n^\omega)$ problem and $O(n^2)$ would be a breakthrough.
András Salamon
CC BY-SA 2.5
2010-09-29T15:11:17.287Z
@Per: bounding indegree and levels is not enough, I think even indegree 2 is enough if the DAG is sufficiently like an expander.
András Salamon
CC BY-SA 2.5
2010-09-29T22:18:00.980Z
@Per: I am not claiming that the unit-weight case has been solved.  I am just claiming that if the weights are positive integers bounded by O(1), then the problem is no harder than the unit-weight case (and I forgot to state “positive” in the previous comment).  As for another version of the problem, I do not know what “the growth in size of the generations (a la topological sort)” means.  Can you elaborate?
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T22:42:26.027Z
@András: Thanks!  I improved the answer using your comment (in revision 4).
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-29T02:31:21.470Z
2010-09-30T11:18:46.780Z
2010-09-30T11:18:46.780Z
Tsuyoshi Ito
<p>This is an expansion of my comment on Tsuyoshi's answer.  I think the negative answer to the question can be made unconditional.</p>

<p>This problem seems to require $\omega(n)$ addition operations in the worst case, even for graphs with $O(n)$ edges.  Hence it does not seem possible to attain the required bound.</p>

<p>Consider a graph $G_{r,c}$ consisting of $r \times c$ vertices, arranged in a grid.  The vertices in each of the $r$ rows depend on precisely two vertices in the row above.  The family consists of graphs like this, for suitable combinations of values of $r$ and $c$, and suitable arrangements of edges.</p>

<p>In particular, let $r = (\log\ n)/2$ and $c = 2n/\log\ n$.  Also, let the weights of the top row vertices be distinct powers of 2.</p>

<p>Each of the vertices in the bottom row will then depend on $\sqrt{n}$ vertices in the top row.  As far as I can tell, there then exists a specific DAG with different values for each of the bottom row weights, such that $\omega(\log\ n)$ non-reusable additions are required on average for each of these sums.</p>

<p>Overall this yields an $\omega(n)$ lower bound for the number of additions, while the number of edges is $2c(r-1) = O(n)$.</p>

<p>The point seems to be that the underlying partial order is dense, but the DAG represents its transitive reduction, which can be sparse.</p>

CC BY-SA 2.5
2010-10-01T18:37:18.653Z
This argument is interesting, but I am not sure if it can be made into a proof of any interesting statement.  Considering the pervasive difficulty of proving lower bounds of problems, this argument seems handwavy to me.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-01T20:03:54.480Z
@Tsuyoshi: I think the existence should work via a probabilistic argument, and the lower bound is weak so there seems to be enough space for it to work.  But you are right, it is handwavy, that phrase "non-reusable additions on average" needs a better foundation.
András Salamon
CC BY-SA 2.5
2010-09-30T10:49:16.923Z
2010-09-30T10:49:16.923Z
András Salamon
<p>There is an algorithm work faster than <span class="math-container">$O(VE)$</span> in some very specific case, if you can make the digraph (after removing edges that preserve reachability of vertices) isomorphic to a minor of <span class="math-container">$P(a_1, a_2,...a_k)$</span> then the complexity will be about <span class="math-container">$O(Vk^2)$</span> where</p>
<ul>
<li>a graph <span class="math-container">$H$</span> is a minor of graph <span class="math-container">$G$</span> i.f.f we can obtain <span class="math-container">$H$</span> by first delete some vertices of <span class="math-container">$G$</span> then,choose some <span class="math-container">$u$</span>, <span class="math-container">$v$</span> and a path from <span class="math-container">$u$</span> to <span class="math-container">$v$</span>, remove every vertex that is not <span class="math-container">$u,v$</span> in that path and replace by an edge.</li>
<li><span class="math-container">$P(a_1, a_2,...a_k)$</span> is the digraph with vertices are tuples <span class="math-container">$(b_1, b_2,...b_k)$</span> such that <span class="math-container">$0 \le b_i \le a_i$</span> and there is a directed edge from <span class="math-container">$(b_1, b_2,...b_k)$</span> to <span class="math-container">$(c_1, c_2,...c_k)$</span> i.f.f there exist an <span class="math-container">$i$</span> that <span class="math-container">$b_j  = c_j $</span> for <span class="math-container">$j \not = i$</span> and <span class="math-container">$b_i = c_i + 1$</span></li>
</ul>
<p>Now, lets solve the problem in <span class="math-container">$P(a_1, a_2,...a_k)$</span>, let <span class="math-container">$\sigma(u, j)$</span> be the total sum of weights of the ancestors <span class="math-container">$v$</span> of <span class="math-container">$u$</span> s.t <span class="math-container">$v_i = u_i$</span> for every <span class="math-container">$i \le j$</span>, the answer for the vertex <span class="math-container">$u$</span> is <span class="math-container">$\sigma(u, 0)$</span></p>
<p>We can recursively calculate every <span class="math-container">$\sigma(u, j)$</span> via BFS from the root in <span class="math-container">$O(k)$</span> as
<span class="math-container">$$\sigma(u,j) = w(u) + \sum_{i=j+1}^k \sigma(u \uparrow i, i-1)$$</span>
where <span class="math-container">$u \uparrow i$</span> is the vector <span class="math-container">$u$</span> but replace <span class="math-container">$u_i$</span> with <span class="math-container">$u_i + 1$</span>  ( if <span class="math-container">$u \uparrow i$</span> is not in <span class="math-container">$P(a_1, a_2, ... a_k)$</span> we just ignore it)</p>
<p>Now, return to the main problem, assume we have found such minor with the isomorphism <span class="math-container">$f$</span>, note that for all in edges <span class="math-container">$e_i$</span> to <span class="math-container">$u$</span> the path <span class="math-container">$f(e_i)$</span> is pairwie disjoint by the definition of minor, so we know that which is the edge <span class="math-container">$f(u) \uparrow i$</span> will associated with, hence we can calculate every <span class="math-container">$\sigma(u,0)$</span> in <span class="math-container">$O(|V|k^2)$</span></p>
<p>comment: The minors of <span class="math-container">$P(a_1, a_2, ... a_k)$</span> is surprisingly not very uncommon, if  every vertex has injection <span class="math-container">$f$</span> into a subset of <span class="math-container">${1,2...k}$</span> and <span class="math-container">$u\to v \iff f(u) \supset f(v)$</span>, or <span class="math-container">$f$</span> is an injection into the divisors of some integers with <span class="math-container">$k$</span> prime factors. I wonder can we generalize this approach further for example to every digraph with maximum degreee <span class="math-container">$k$</span> ?</p>

CC BY-SA 4.0
2024-11-14T18:32:29.113Z
2024-11-14T18:37:38.937Z
2024-11-14T18:37:38.937Z
jackdean
<p><strong>This is wrong and is based on a misunderstanding on the question.</strong>  Thanks to Tsuyoshi for patiently pointing out my error.  Leaving up in case others make the same mistake.</p>

<p>If the number of immediate predecessors of a node is bounded by $k$, then an algorithm that first does a topological sort, then processes the nodes in this order will do the job.  <em>Measuring the number of immediate predecessors is suggested by viewing the DAG as a partial order.  A model with bounded number of immediate predecessors may be appropriate for a revision history, where only a few files are changed by most revisions.</em></p>

<p>The point is that <strong>for this special case</strong>, for each node there are at most $k$ predecessors in the linear order that need to be looked at, so this can be done with $O(k|V|)$ additions.</p>

<p>The <a href="http://en.wikipedia.org/wiki/Topological_sorting" rel="nofollow">topological sort</a> requires $O(|V|+|E|)$ time, which gives you the asymptotic bound you are looking for.  But in the application you describe, the linear number of additions is likely to dominate.</p>

<p>This approach should also work well if there are some nodes with many immediate predecessors, as long as they are relatively infrequent.</p>

CC BY-SA 2.5
2010-09-27T21:56:04.883Z
I do not get it.  How do you avoid the double-counting when the DAG is not a tree?  In fact, if I am not mistaken, the general case can be reduced to the case where each vertex has at most two predecessors, and any linear-time algorithm for the latter case gives a line-time algorithm for the general case.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-28T17:22:16.957Z
The requested bound was $O(|V|+|E|)$ and the remark about double counting seems besides the point.  The bounded number of immediate predecessors seems enough; each value is used in at most $k$ partial sums.
András Salamon
CC BY-SA 2.5
2010-09-28T18:55:55.350Z
I am afraid that you misunderstood my comment.  I am questioning the correctness of your algorithm, not the running time.  Suppose a DAG with four vertices A, B, C, D with edges A→B→D and A→C→D with each vertex given some weight.  After computing the partial sums for B and C, you cannot simply add the partial sums for B and C to compute the sum for D because doing so would add the weight of the vertex A twice.
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-28T19:15:34.887Z
@Tsuyoshi: so the semantics is meant to be "compute $\sum_{u < v} w(u)$"?  I have then misunderstood the question, summing over all predecessor paths.
András Salamon
CC BY-SA 2.5
2010-09-28T19:26:56.470Z
Yes.  And now I remember that the first time I saw this question, I misread the question in the same way and thought it would be obvious.  But no, the real question is more difficult than that.  Time to think….
Tsuyoshi Ito
CC BY-SA 2.5
2010-09-27T20:13:04.467Z
2010-09-28T19:17:16.240Z
2010-09-28T19:17:16.240Z
András Salamon
<p>The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis diffusion), but increasing its precision is exponential in the number of bits (and I need a lot of bits).</p>

<p>Background: this task is done (several times with different 'weights') as part of the probability calculations in  BBChop (http://github.com/ealdwulf/bbchop) a program for finding intermittent bugs (ie, a bayesian version of 'git bisect'). The DAG in question is therefore a  revision history. That means that the number of edges is unlikely to approach the square of the number of nodes, it's likely to be less than k times the number of nodes for some smallish k. 
Unfortunately I haven't found any other useful properties of revision DAGs. For example, I was hoping that the largest triconnected component would grow only as the square-root of the number of nodes, but sadly (at least in the history of the linux kernel) it grows linearly.  </p>

CC BY-SA 2.5
2010-08-29T12:07:39.330Z
Just to clarify: it's only the nodes that have weights, not the edges?
Heinrich Apfelmus
CC BY-SA 2.5
2010-08-29T12:22:28.967Z
Yes, just the nodes.
Ealdwulf
CC BY-SA 2.5
2010-08-29T17:23:31.967Z
This seems to be a near-duplicate of http://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag ?
Jukka Suomela
CC BY-SA 2.5
2010-08-29T20:27:38.980Z
this actually seems more general, since assigning unit weights to all vertices reduces this problem to the reachability problem.
Suresh Venkat
CC BY-SA 2.5
2010-09-02T01:36:27.697Z
Approximation seems not to hard to do with some extra polylog factors...
Sariel Har-Peled
CC BY-SA 2.5
2010-09-04T09:48:23.480Z
Sariel: could you elaborate on that?
Ealdwulf
CC BY-SA 2.5
2010-09-13T03:43:20.907Z
I might have to quickly withdraw my comment... What do you mean by many bits? Do you need an approximation that is $(1\pm \epsilon)*$true weight, for some fixed $\epsilon$ or do you need a stronger approximation? I can do this kind of approximation for arbitrary positive weights, but not for arbitrary precision.
Sariel Har-Peled
CC BY-SA 2.5
2010-09-19T21:14:05.207Z
Um, I don't really have a good definition of the needed accuracy at the moment. My program didn't work until I used mpmath floats with 200 bits of precision, but it's possible that it can be rearranged to require less.
Ealdwulf
CC BY-SA 2.5
2010-09-27T14:45:32.910Z
Suresh, you mean assigning a unit weight to your source (and zero to everything else) reduces reachability to this problem?
Derrick Stolee
CC BY-SA 2.5
2010-09-27T14:47:18.367Z
Ah, I see, you reduce the linked question to this one.
Derrick Stolee
<ds.algorithms><graph-theory><directed-acyclic-graph>
Given a weighted DAG, is there an $O(V+E)$-time algorithm to replace each weight with the sum of its ancestor weights?
Ealdwulf
# Given a weighted DAG, is there an $O(V+E)$-time algorithm to replace each weight with the sum of its ancestor weights?

(Asked by: username_0 on 2010-08-29)

The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in reasonable time is an approximate one (Synopsis diffusion), but increasing its precision is exponential in the number of bits (and I need a lot of bits).

Background: this task is done (several times with different 'weights') as part of the probability calculations in BBChop (http://github.com/ealdwulf/bbchop) a program for finding intermittent bugs (ie, a bayesian version of 'git bisect'). The DAG in question is therefore a revision history. That means that the number of edges is unlikely to approach the square of the number of nodes, it's likely to be less than k times the number of nodes for some smallish k.
Unfortunately I haven't found any other useful properties of revision DAGs. For example, I was hoping that the largest triconnected component would grow only as the square-root of the number of nodes, but sadly (at least in the history of the linux kernel) it grows linearly.

**Tags:** ds.algorithms, graph-theory, directed-acyclic-graph
> **Comments:**
> **username_1**: Just to clarify: it's only the nodes that have weights, not the edges?  
> **username_0**: Yes, just the nodes.  
> **username_2**: This seems to be a near-duplicate of http://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag ?  
> **username_3**: this actually seems more general, since assigning unit weights to all vertices reduces this problem to the reachability problem.  
> **username_4**: Approximation seems not to hard to do with some extra polylog factors...  
> **username_0**: Sariel: could you elaborate on that?  
> **username_4**: I might have to quickly withdraw my comment... What do you mean by many bits? Do you need an approximation that is $(1\pm \epsilon)*$true weight, for some fixed $\epsilon$ or do you need a stronger approximation? I can do this kind of approximation for arbitrary positive weights, but not for arbitrary precision.  
> **username_0**: Um, I don't really have a good definition of the needed accuracy at the moment. My program didn't work until I used mpmath floats with 200 bits of precision, but it's possible that it can be rearranged to require less.  
> **username_5**: Suresh, you mean assigning a unit weight to your source (and zero to everything else) reduces reachability to this problem?  
> **username_5**: Ah, I see, you reduce the linked question to this one.  

---

## 4 answers

### Answer by username_6 on 2010-09-29. Score: 18

We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2*n*. Then the current task cannot be performed even in a slightly weaker time bound O(*n*2), unless the transitive closure of an arbitrary directed graph can be computed in O(*n*2) time, where *n* denotes the number of vertices. (Note that an O(*n*2)-time algorithm for the transitive closure will be a breakthrough.) This is the contrapositive of the following claim:

**Claim**. If the current task can be performed in time O(*n*2), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(*n*2) time (assuming some reasonable computational model).

**Proof**. As a preprocessing, we compute the strongly connected component decomposition of the given directed graph *G* in time O(*n*2) to obtain a DAG *G*′. Note that if we can compute the transitive closure of *G*′, we can reconstruct the transitive closure of *G*.

Now assign the weight 2*i* to each vertex *i* of the DAG *G*′ and use the algorithm for the current problem. Then the binary representation of the sum assigned to each vertex *i* describes exactly the set of ancestors of *i*, in other words, we have computed the transitive closure of *G*′. **QED**.

The converse of the claim also holds: if you can compute the transitive closure of a given DAG, it is easy to compute the required sums by additional work in time O(*n*2). Therefore, in theory you can achieve the current task in time O(*n*2.376) by using the algorithm for the transitive closure based on the [Coppersmith-Winograd matrix multiplication algorithm](http://en.wikipedia.org/wiki/Coppersmith%E2%80%93Winograd_algorithm).

*Edit*: Revision 2 and earlier did not state the assumption about the range of vertex weights explicitly. Per Vognsen pointed out in a comment that this implicit assumption may not be reasonable (thanks!), and I agree. Even if arbitrary weights are not needed in applications, I guess that this answer might rule out some approaches by the following line of reasoning: “If this approach worked, it would give an algorithm for the arbitrary weights, which is ruled out unless the transitive closure can be computed in time O(*n*2).”

*Edit*: Revision 4 and earlier stated the direction of edges incorrectly.

> **Comments:**
> **username_7**: I was thinking about this very thing last night since one practical solution uses bit vectors to do the exclusion counting. I guess the only question is whether it's reasonable to assume that the weights can have bit length proportional to n. In practice, I can imagine the weights are bounded by some k so that the maximal possible sum is kn, which isn't enough bits to pull this trick.  
> **username_6**: @Per: I agree that the assumption that vertex weights can be n-bit integers might be questionable.  I edited the answer to make this assumption explicit.  Thanks!  
> **username_6**: @Per: I realized that if the vertex weights are integers bounded by O(1), the problem reduces to [the case where all vertices have weight 1](http://cstheory.stackexchange.com/questions/553/what-bounds-can-be-put-on-counting-reachable-nodes-in-a-dag) by duplicating vertices in a suitable way.  
> **username_7**: Unfortunately I don't see an answer in that thread to the counting problem. The counts contain logarithmically less information than the listing of the transitive closure, O(n log n) vs O(n^2), so I don't see how a straightforward reduction could work.  
> **username_7**: By the way, an interesting version of this problem is when we have a bound on the branch factor and information on the growth in size of the generations (a la topological sort) of the DAG. If the growth is exponential, the pattern is essentially tree-like. What if it's linear, log-linear, quadratic, etc?  
> **username_8**: Nice argument!  It perhaps worth noting that the asymptotically best algorithm for transitive closure is via matrix multiplication.  So this is a $O(n^\omega)$ problem and $O(n^2)$ would be a breakthrough.  
> **username_8**: @Per: bounding indegree and levels is not enough, I think even indegree 2 is enough if the DAG is sufficiently like an expander.  
> **username_6**: @Per: I am not claiming that the unit-weight case has been solved.  I am just claiming that if the weights are positive integers bounded by O(1), then the problem is no harder than the unit-weight case (and I forgot to state “positive” in the previous comment).  As for another version of the problem, I do not know what “the growth in size of the generations (a la topological sort)” means.  Can you elaborate?  
> **username_6**: @András: Thanks!  I improved the answer using your comment (in revision 4).  

---

### Answer by username_8 on 2010-09-30. Score: 2

This is an expansion of my comment on Tsuyoshi's answer. I think the negative answer to the question can be made unconditional.

This problem seems to require $\omega(n)$ addition operations in the worst case, even for graphs with $O(n)$ edges. Hence it does not seem possible to attain the required bound.

Consider a graph $G\_{r,c}$ consisting of $r \times c$ vertices, arranged in a grid. The vertices in each of the $r$ rows depend on precisely two vertices in the row above. The family consists of graphs like this, for suitable combinations of values of $r$ and $c$, and suitable arrangements of edges.

In particular, let $r = (\log\ n)/2$ and $c = 2n/\log\ n$. Also, let the weights of the top row vertices be distinct powers of 2.

Each of the vertices in the bottom row will then depend on $\sqrt{n}$ vertices in the top row. As far as I can tell, there then exists a specific DAG with different values for each of the bottom row weights, such that $\omega(\log\ n)$ non-reusable additions are required on average for each of these sums.

Overall this yields an $\omega(n)$ lower bound for the number of additions, while the number of edges is $2c(r-1) = O(n)$.

The point seems to be that the underlying partial order is dense, but the DAG represents its transitive reduction, which can be sparse.

> **Comments:**
> **username_6**: This argument is interesting, but I am not sure if it can be made into a proof of any interesting statement.  Considering the pervasive difficulty of proving lower bounds of problems, this argument seems handwavy to me.  
> **username_8**: @Tsuyoshi: I think the existence should work via a probabilistic argument, and the lower bound is weak so there seems to be enough space for it to work.  But you are right, it is handwavy, that phrase "non-reusable additions on average" needs a better foundation.  

---

### Answer by username_9 on 2024-11-14. Score: 0

There is an algorithm work faster than $O(VE)$ in some very specific case, if you can make the digraph (after removing edges that preserve reachability of vertices) isomorphic to a minor of $P(a\_1, a\_2,...a\_k)$ then the complexity will be about $O(Vk^2)$ where

* a graph $H$ is a minor of graph $G$ i.f.f we can obtain $H$ by first delete some vertices of $G$ then,choose some $u$, $v$ and a path from $u$ to $v$, remove every vertex that is not $u,v$ in that path and replace by an edge.
* $P(a\_1, a\_2,...a\_k)$ is the digraph with vertices are tuples $(b\_1, b\_2,...b\_k)$ such that $0 \le b\_i \le a\_i$ and there is a directed edge from $(b\_1, b\_2,...b\_k)$ to $(c\_1, c\_2,...c\_k)$ i.f.f there exist an $i$ that $b\_j = c\_j $ for $j \not = i$ and $b\_i = c\_i + 1$

Now, lets solve the problem in $P(a\_1, a\_2,...a\_k)$, let $\sigma(u, j)$ be the total sum of weights of the ancestors $v$ of $u$ s.t $v\_i = u\_i$ for every $i \le j$, the answer for the vertex $u$ is $\sigma(u, 0)$

We can recursively calculate every $\sigma(u, j)$ via BFS from the root in $O(k)$ as
$$\sigma(u,j) = w(u) + \sum\_{i=j+1}^k \sigma(u \uparrow i, i-1)$$
where $u \uparrow i$ is the vector $u$ but replace $u\_i$ with $u\_i + 1$ ( if $u \uparrow i$ is not in $P(a\_1, a\_2, ... a\_k)$ we just ignore it)

Now, return to the main problem, assume we have found such minor with the isomorphism $f$, note that for all in edges $e\_i$ to $u$ the path $f(e\_i)$ is pairwie disjoint by the definition of minor, so we know that which is the edge $f(u) \uparrow i$ will associated with, hence we can calculate every $\sigma(u,0)$ in $O(|V|k^2)$

comment: The minors of $P(a\_1, a\_2, ... a\_k)$ is surprisingly not very uncommon, if every vertex has injection $f$ into a subset of ${1,2...k}$ and $u\to v \iff f(u) \supset f(v)$, or $f$ is an injection into the divisors of some integers with $k$ prime factors. I wonder can we generalize this approach further for example to every digraph with maximum degreee $k$ ?


---

### Answer by username_8 on 2010-09-27. Score: -2

**This is wrong and is based on a misunderstanding on the question.** Thanks to Tsuyoshi for patiently pointing out my error. Leaving up in case others make the same mistake.

If the number of immediate predecessors of a node is bounded by $k$, then an algorithm that first does a topological sort, then processes the nodes in this order will do the job. *Measuring the number of immediate predecessors is suggested by viewing the DAG as a partial order. A model with bounded number of immediate predecessors may be appropriate for a revision history, where only a few files are changed by most revisions.*

The point is that **for this special case**, for each node there are at most $k$ predecessors in the linear order that need to be looked at, so this can be done with $O(k|V|)$ additions.

The [topological sort](http://en.wikipedia.org/wiki/Topological_sorting) requires $O(|V|+|E|)$ time, which gives you the asymptotic bound you are looking for. But in the application you describe, the linear number of additions is likely to dominate.

This approach should also work well if there are some nodes with many immediate predecessors, as long as they are relatively infrequent.

> **Comments:**
> **username_6**: I do not get it.  How do you avoid the double-counting when the DAG is not a tree?  In fact, if I am not mistaken, the general case can be reduced to the case where each vertex has at most two predecessors, and any linear-time algorithm for the latter case gives a line-time algorithm for the general case.  
> **username_8**: The requested bound was $O(|V|+|E|)$ and the remark about double counting seems besides the point.  The bounded number of immediate predecessors seems enough; each value is used in at most $k$ partial sums.  
> **username_6**: I am afraid that you misunderstood my comment.  I am questioning the correctness of your algorithm, not the running time.  Suppose a DAG with four vertices A, B, C, D with edges A→B→D and A→C→D with each vertex given some weight.  After computing the partial sums for B and C, you cannot simply add the partial sums for B and C to compute the sum for D because doing so would add the weight of the vertex A twice.  
> **username_8**: @Tsuyoshi: so the semantics is meant to be "compute $\sum_{u < v} w(u)$"?  I have then misunderstood the question, summing over all predecessor paths.  
> **username_6**: Yes.  And now I remember that the first time I saw this question, I misread the question in the same way and thought it would be obvious.  But no, the real question is more difficult than that.  Time to think….  

---

