<p>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: <a href="http://www.computer.org/portal/web/csdl/doi/10.1109/ACSSC.1995.540810">http://www.computer.org/portal/web/csdl/doi/10.1109/ACSSC.1995.540810</a> .</p>

CC BY-SA 2.5
2010-08-26T16:52:02.307Z
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
CC BY-SA 2.5
2010-08-26T14:27:52.567Z
2010-08-26T14:27:52.567Z
Bart Jansen
<p>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)).</p>

CC BY-SA 2.5
2010-08-29T22:01:21.880Z
2010-08-29T22:01:21.880Z
Ealdwulf
<p>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</p>

CC BY-SA 2.5
2010-09-09T00:05:02.523Z
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
CC BY-SA 2.5
2010-09-20T08:30:28.827Z
Note that this results apply to all directed graph, not just DAGs.
tonfa
CC BY-SA 2.5
2010-09-22T15:10:08.263Z
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
CC BY-SA 2.5
2010-09-05T05:11:22.127Z
2010-09-05T05:11:22.127Z
virgi
<p>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)?</p>

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

<p>Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts <em>paths</em>, not reachable <em>nodes</em>. (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.</p>

CC BY-SA 2.5
2010-08-29T20:28:47.027Z
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
CC BY-SA 2.5
2010-08-31T08:31:55.880Z
@Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question.
Radu GRIGore
<ds.algorithms><graph-theory>
What bounds can be put on counting reachable nodes in a dag?
Radu GRIGore
# What bounds can be put on counting reachable nodes in a dag?

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

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.

**Tags:** ds.algorithms, graph-theory
> **Comments:**
> **username_1**: 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  
> **username_0**: @Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question.  

---

## 3 answers

### Answer by username_4 on 2010-09-05. Score: 10 | Accepted answer

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

> **Comments:**
> **username_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.  
> **username_5**: Note that this results apply to all directed graph, not just DAGs.  
> **username_4**: 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  

---

### Answer by username_2 on 2010-08-26. Score: 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> .

> **Comments:**
> **username_0**: 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.  

---

### Answer by username_3 on 2010-08-29. Score: 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)).


---

