Given a weighted DAG, is there an $O(V+E)$-time algorithm to replace each weight with the sum of its ancestor weights?

Question

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.

Answer 1

We assume that vertex weights can be arbitrary positive integers, or more precisely, they can be positive integers at most 2ⁿ. Then the current task cannot be performed even in a slightly weaker time bound O(n²), unless the transitive closure of an arbitrary directed graph can be computed in O(n²) time, where n denotes the number of vertices. (Note that an O(n²)-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²), the transitive closure of an arbitrary directed graph given as its adjacency matrix can be computed in O(n²) 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²) 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ⁱ 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²). 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.

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²).”

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

Answer 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.

Answer 3

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 4

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