34
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Just to clarify: it's only the nodes that have weights, not the edges? $\endgroup$ – Heinrich Apfelmus Aug 29 '10 at 12:07
  • $\begingroup$ Yes, just the nodes. $\endgroup$ – Ealdwulf Aug 29 '10 at 12:22
  • 4
    $\begingroup$ This seems to be a near-duplicate of cstheory.stackexchange.com/questions/553/… ? $\endgroup$ – Jukka Suomela Aug 29 '10 at 17:23
  • $\begingroup$ this actually seems more general, since assigning unit weights to all vertices reduces this problem to the reachability problem. $\endgroup$ – Suresh Venkat Aug 29 '10 at 20:27
  • $\begingroup$ Approximation seems not to hard to do with some extra polylog factors... $\endgroup$ – Sariel Har-Peled Sep 2 '10 at 1:36
16
$\begingroup$

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

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 29 '10 at 3:21
  • $\begingroup$ @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! $\endgroup$ – Tsuyoshi Ito Sep 29 '10 at 4:15
  • 1
    $\begingroup$ @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 by duplicating vertices in a suitable way. $\endgroup$ – Tsuyoshi Ito Sep 29 '10 at 4:26
  • $\begingroup$ 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. $\endgroup$ – Per Vognsen Sep 29 '10 at 4:33
  • $\begingroup$ 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? $\endgroup$ – Per Vognsen Sep 29 '10 at 4:40
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Oct 1 '10 at 18:37
  • $\begingroup$ @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. $\endgroup$ – András Salamon Oct 1 '10 at 20:03
-2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 27 '10 at 21:56
  • $\begingroup$ 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. $\endgroup$ – András Salamon Sep 28 '10 at 17:22
  • $\begingroup$ 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. $\endgroup$ – Tsuyoshi Ito Sep 28 '10 at 18:55
  • $\begingroup$ @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. $\endgroup$ – András Salamon Sep 28 '10 at 19:15
  • 1
    $\begingroup$ 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…. $\endgroup$ – Tsuyoshi Ito Sep 28 '10 at 19:26

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.