<p>The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "<a href="http://dx.doi.org/10.1006/jcss.1997.1534" rel="nofollow">Size-Estimation Framework with Applications to Transitive Closure and Reachability</a>" by Edith Cohen.</p>

CC BY-SA 3.0
2014-04-16T06:07:50.750Z
2016-10-19T07:39:33.410Z
2016-10-19T07:39:33.410Z
user22547
<p>I am not a expert here i will a try.</p>

<p>1) Since it is DAG, it should have a sink vertex i.e vertex with outdegree 0. Find a sink vertex say x and add {x} as reachable vertex to Neighbor(x). remove x and repeat the process till graph becomes empty  </p>

CC BY-SA 2.5
2011-03-20T22:13:10.847Z
Since the _out-degree_ is bounded, it would seem to be more useful to start with a source?
András Salamon
CC BY-SA 3.0
2011-04-19T11:27:59.250Z
@andras-salamon: no, because you don't trivially know how many nodes are reachable from a source. You do no that (zero) for a sink though.
Martin B.
CC BY-SA 3.0
2013-11-29T18:35:58.660Z
The running time of this algorithm is also $O(|V| \cdot |E|)$ -- so no better than what was described in the question.  At each step, the vertex $x$ that you are considering may have a set of $O(|V|)$ reachable vertices; you add this to each of its neighbors, which takes $O(|V|)$ time per neighbor.  In total, you do $O(|V|)$ work per edge, for a total of $O(|V| \cdot |E|)$ work.
D.W.
CC BY-SA 2.5
2011-03-20T07:56:46.473Z
2011-03-20T07:56:46.473Z
Prabu 
<p>(Similar to Prabu's solution ... but more detailed)</p>

<p>Let $N(v)$ be the (out) neighbors of $v$ and $reach(v)$ denote the number of vertices reachable from v.</p>

<ol>
<li>do a topological sort. (possible in $O(|V|+|E|)$)</li>
<li>starting from the end of the list (at a sink-end): 
For each vertex $v$ (starting at the sink-end of the list):
    $reach(v) = \sum_{n\in N(v)} reach(n)$.</li>
</ol>

<p>The second part traverses every edge once, adding another $|E|$, so in total I get $O(|V|+|E|)$.</p>

CC BY-SA 4.0
2020-06-15T23:22:32.693Z
Yes but your recurrence for reach$(v)$ is not correct.  As given it would count the number of _paths_ out of $v$, which can be more than the number of vertices reachable from $v$.  (I.e., it double counts; see http://cstheory.stackexchange.com/q/736/236.)
Neal Young
CC BY-SA 3.0
2011-04-19T15:35:42.913Z
2011-04-19T15:35:42.913Z
Martin B.
<p>Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running <em>dfs</em> from every vertex and this will take $O(|V||E|)$ time. Is there a better way to solve this problem?</p>

CC BY-SA 2.5
2011-01-11T17:45:32.623Z
Related: http://cstheory.stackexchange.com/q/736/236 http://cstheory.stackexchange.com/q/553/236
Radu GRIGore
CC BY-SA 2.5
2011-01-11T21:00:23.787Z
@Radu is this a straight up duplicate ? it does sound like it
Suresh Venkat
CC BY-SA 2.5
2011-01-11T22:18:31.347Z
@Suresh, compared to my question this one has an upper bound on vertex degree and does not ask for lower bounds. These are small differences in my opinion, so I'd consider it a duplicate, but I don't feel strongly about it.
Radu GRIGore
CC BY-SA 2.5
2011-01-11T22:54:41.287Z
ok so we'll leave it as is.
Suresh Venkat
CC BY-SA 2.5
2011-01-12T14:47:24.180Z
virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one.
Radu GRIGore
CC BY-SA 2.5
2011-01-12T18:07:26.000Z
@Radu: You're correct, I've removed my answer which is slower than that.
Hsien-Chih Chang 張顯之
<ds.algorithms><graph-theory><graph-algorithms><directed-acyclic-graph>
Number of reachable vertices in DAG for every vertex
MikleB
# Number of reachable vertices in DAG for every vertex

(Asked by: username_0 on 2011-01-11)

Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running *dfs* from every vertex and this will take $O(|V||E|)$ time. Is there a better way to solve this problem?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, directed-acyclic-graph

> **Comments:**
> **username_1**: Related: http://cstheory.stackexchange.com/q/736/236 http://cstheory.stackexchange.com/q/553/236  
> **username_2**: @Radu is this a straight up duplicate ? it does sound like it  
> **username_1**: @Suresh, compared to my question this one has an upper bound on vertex degree and does not ask for lower bounds. These are small differences in my opinion, so I'd consider it a duplicate, but I don't feel strongly about it.  
> **username_2**: ok so we'll leave it as is.  
> **username_1**: virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one.  
> **username_3**: @Radu: You're correct, I've removed my answer which is slower than that.  

---

## 3 answers

### Answer by username_4 on 2014-04-16. Score: 6

The best exact algorithm will run in time O( min{mn, n^2.38} ) by using fast binary matrix multiplication. However, there is a random algorithm, which runs in time O(m+n) and estimates the number of reachable nodes from each node with a small relative error, please refer to paper "[Size-Estimation Framework with Applications to Transitive Closure and Reachability](http://dx.doi.org/10.1006/jcss.1997.1534)" by Edith Cohen.


---

### Answer by username_5 on 2011-03-20. Score: -2

I am not a expert here i will a try.

1) Since it is DAG, it should have a sink vertex i.e vertex with outdegree 0. Find a sink vertex say x and add {x} as reachable vertex to Neighbor(x). remove x and repeat the process till graph becomes empty

> **Comments:**
> **username_6**: Since the _out-degree_ is bounded, it would seem to be more useful to start with a source?  
> **username_7**: @andras-salamon: no, because you don't trivially know how many nodes are reachable from a source. You do no that (zero) for a sink though.  
> **username_8**: The running time of this algorithm is also $O(|V| \cdot |E|)$ -- so no better than what was described in the question.  At each step, the vertex $x$ that you are considering may have a set of $O(|V|)$ reachable vertices; you add this to each of its neighbors, which takes $O(|V|)$ time per neighbor.  In total, you do $O(|V|)$ work per edge, for a total of $O(|V| \cdot |E|)$ work.  

---

### Answer by username_7 on 2011-04-19. Score: -2

(Similar to Prabu's solution ... but more detailed)

Let $N(v)$ be the (out) neighbors of $v$ and $reach(v)$ denote the number of vertices reachable from v.

1. do a topological sort. (possible in $O(|V|+|E|)$)
2. starting from the end of the list (at a sink-end):
   For each vertex $v$ (starting at the sink-end of the list):
   $reach(v) = \sum\_{n\in N(v)} reach(n)$.

The second part traverses every edge once, adding another $|E|$, so in total I get $O(|V|+|E|)$.

> **Comments:**
> **username_9**: Yes but your recurrence for reach$(v)$ is not correct.  As given it would count the number of _paths_ out of $v$, which can be more than the number of vertices reachable from $v$.  (I.e., it double counts; see http://cstheory.stackexchange.com/q/736/236.)  

---

