# What bounds can be put on counting reachable nodes in a dag?

Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be improved (related: what exactly is known about lower bounds for transitive closure)?

Motivation: I had to do this a couple of times while representing fol formulas as dags.

Edit: Please note that simply doing $c_x=1+\sum_{x\to y}c_y$ counts paths, not reachable nodes. (I added this because apparently many people thought this simple solution would work by the votes I saw on a now-deleted answer.) In fact, this problem appears precisely when you want to do something interesting with 'shared' parts, nodes reachable by more than one path. Also, I say dag, because if they are solved, then solving digraphs is easy.

• This appears to be a special case (setting all weights to one) of cstheory.stackexchange.com/questions/736/… – Suresh Venkat Aug 29 '10 at 20:28
• @Suresh: Whether arbitrary weights make the problem harder seems to me like another interesting question. – Radu GRIGore Aug 31 '10 at 8:31

The transitive closure of a directed graph with $m$ edges and $n$ vertices can be computed slightly faster than $O(mn)$ time, but not by much. An $O(n^2 + mn/\log n)$ time algorithm is mentioned in a footnote of Chan's 2005 WADS paper on APSP (journal version in Algorithmica 2008). A slight improvement to $O(n^2 + mn \log(n^2/m)/\log^2 n)$ can be found in the ICALP'08 paper "A New Combinatorial Approach for Sparse Graph Problems " by Blelloch, Vassilevska and Williams. That being said, I don't know whether counting descendents is easier than actually finding them
I think you can use matrix multiplication to compute the transitive closure of the DAG, and then use the number of out-neighbors as the desired counts. I'm no expert on the literature but I think you can compute the transitive closure in the same time as matrix multiplication, i.e. $n^{\omega}$ time: http://www.computer.org/portal/web/csdl/doi/10.1109/ACSSC.1995.540810 .