# Number of reachable vertices in DAG for every vertex

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?

• Jan 11 '11 at 17:45
• @Radu is this a straight up duplicate ? it does sound like it Jan 11 '11 at 21:00
• @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. Jan 11 '11 at 22:18
• ok so we'll leave it as is. Jan 11 '11 at 22:54
• virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one. Jan 12 '11 at 14:47

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" by Edith Cohen.

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

• Since the out-degree is bounded, it would seem to be more useful to start with a source? Mar 20 '11 at 22:13
• @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. Apr 19 '11 at 11:27
• 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.
Nov 29 '13 at 18:35

(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|)$.

• 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 cstheory.stackexchange.com/q/736/236.) Jun 15 '20 at 23:22