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?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Related: cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236 $\endgroup$– Radu GRIGoreJan 11, 2011 at 17:45
-
1$\begingroup$ @Radu is this a straight up duplicate ? it does sound like it $\endgroup$– Suresh VenkatJan 11, 2011 at 21:00
-
$\begingroup$ @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. $\endgroup$– Radu GRIGoreJan 11, 2011 at 22:18
-
1$\begingroup$ ok so we'll leave it as is. $\endgroup$– Suresh VenkatJan 11, 2011 at 22:54
-
4$\begingroup$ virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one. $\endgroup$– Radu GRIGoreJan 12, 2011 at 14:47
|
Show 1 more comment
3 Answers
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
3
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
-
$\begingroup$ Since the out-degree is bounded, it would seem to be more useful to start with a source? $\endgroup$ Mar 20, 2011 at 22:13
-
$\begingroup$ @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. $\endgroup$ Apr 19, 2011 at 11:27
-
$\begingroup$ 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. $\endgroup$– D.W.Nov 29, 2013 at 18:35
$\begingroup$
$\endgroup$
1
(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|)$.
-
1$\begingroup$ 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.) $\endgroup$ Jun 15, 2020 at 23:22