23

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.

Radu GRIGore
  • 4,796
  • 30
  • 69
  • This appears to be a special case (setting all weights to one) of http://cstheory.stackexchange.com/questions/736/given-a-weighted-dag-is-there-an-ove-algorithm-to-replace-each-weight-with-th – Suresh Venkat Aug 29 '10 at 20:28
  • @Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question. – Radu GRIGore Aug 31 '10 at 08:31

3 Answers3

10

The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams. That being said, I don't know whether counting descendents is easier than actually finding them

virgi
  • 2,489
  • 19
  • 25
  • 4
    Also, look at Edith Cohen's paper "Size-Estimation Framework with Applications to Transitive Closure and Reachability". It gives a randomized algorithm which estimates the number of descendents efficiently. – virgi Sep 09 '10 at 00:05
  • Note that this results apply to all directed graph, not just DAGs. – tonfa Sep 20 '10 at 08:30
  • Yes. The result also applies to the weighted version mentioned in http://cstheory.stackexchange.com/questions/736/given-a-weighted-dag-is-there-an-ove-algorithm-to-replace-each-weight-with-th – virgi Sep 22 '10 at 15:10
7

I think you can use matrix multiplication to compute the transitive closure of the DAG, and then use the number of out-neighbors as the desired counts. I'm no expert on the literature but I think you can compute the transitive closure in the same time as matrix multiplication, i.e. $n^{\omega}$ time: http://www.computer.org/portal/web/csdl/doi/10.1109/ACSSC.1995.540810 .

Bart Jansen
  • 5,265
  • 21
  • 39
  • Thanks, that's interesting! I should add that dags representing symbolic formulas tend to be sparse, so I'm a bit more interested in this case. – Radu GRIGore Aug 26 '10 at 16:52
1

Maybe not useful in your context, but you can get an approximation using Synopsis Diffusion (http://www.cs.cmu.edu/~sknath/sd.htm). I think that makes it O(V+E). Simulating synopsis diffusion on a uniprocessor looks to me to be O(V+E), (you need to do a topological sort first, which is also O(V+E)).

Ealdwulf
  • 562
  • 4
  • 8