11
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Related: cstheory.stackexchange.com/q/736/236 cstheory.stackexchange.com/q/553/236 $\endgroup$ – Radu GRIGore Jan 11 '11 at 17:45
  • 1
    $\begingroup$ @Radu is this a straight up duplicate ? it does sound like it $\endgroup$ – Suresh Venkat Jan 11 '11 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 GRIGore Jan 11 '11 at 22:18
  • 1
    $\begingroup$ ok so we'll leave it as is. $\endgroup$ – Suresh Venkat Jan 11 '11 at 22:54
  • 4
    $\begingroup$ virgi's answer to my question implies a $O(|V|^2)$ algorithm for this one. $\endgroup$ – Radu GRIGore Jan 12 '11 at 14:47
5
$\begingroup$

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.

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Since the out-degree is bounded, it would seem to be more useful to start with a source? $\endgroup$ – András Salamon Mar 20 '11 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$ – Martin B. Apr 19 '11 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 '13 at 18:35
-2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.