Number of reachable vertices in DAG for every vertex

Question

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?

Related: http://cstheory.stackexchange.com/q/736/236 http://cstheory.stackexchange.com/q/553/236 — Radu GRIGore, Jan 11 '11 at 17:45
@Radu is this a straight up duplicate ? it does sound like it — Suresh Venkat, 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. — Radu GRIGore, Jan 11 '11 at 22:18
virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one. — Radu GRIGore, Jan 12 '11 at 14:47
@Radu: You're correct, I've removed my answer which is slower than that. — Hsien-Chih Chang 張顯之, Jan 12 '11 at 18:07

score 6 · Answer 1 · edited Oct 19 '16 at 07:39

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

edited Oct 19 '16 at 07:39

Jan Johannsen

4,630
2
33
50

answered Apr 16 '14 at 06:07

user22547

61
1
2

score -2 · Answer 2 · answered Mar 20 '11 at 07:56

-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

answered Mar 20 '11 at 07:56

Prabu

467
2
14

Since the out-degree is bounded, it would seem to be more useful to start with a source? – András Salamon 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. – Martin B. 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

score -2 · Answer 3 · answered Apr 19 '11 at 15:35

-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.

do a topological sort. (possible in $O(|V|+|E|)$)
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|)$.

answered Apr 19 '11 at 15:35

Martin B.

463
4
10

1

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 Jun 15 '20 at 23:22

Number of reachable vertices in DAG for every vertex

3 Answers3