Finding the Reachability Count for all vertices of a DAG

Question

I am trying to find a fast algorithm with modest space requirements to solve the following problem.

For each vertex of a DAG find the sum of its in-degree and out-degree in the DAG's transitive closure.

Given this DAG:

I expect the following result:

Vertex #   Reacability Count  Reachable Vertices in closure
   7             5            (11, 8, 2, 9, 10)
   5             4            (11, 2, 9, 10)
   3             3            (8, 9, 10)
  11             5            (7, 5, 2, 9, 10)
   8             3            (7, 3, 9)
   2             3            (7, 5, 11)
   9             5            (7, 5, 11, 8, 3)
  10             4            (7, 5, 11, 3)

It seems to me that this should be possible without actually constructing the transitive closure. I haven't been able to find anything on the net that exactly describes this problem. I've got some ideas about how to do this, but I wanted to see what the SO crowd could come up with.

Answer 1

For an exact answer, I think it's going to be hard to beat KennyTM's algorithm. If you're willing to settle for an approximation, then the tank counting method ( http://www.guardian.co.uk/world/2006/jul/20/secondworldwar.tvandradio ) may help.

Assign each vertex a random number in the range [0, 1). Use a linear-time dynamic program like polygenelubricants's to compute for each vertex v the minimum number minreach(v) reachable from v. Then estimate the number of vertices reachable from v as 1/minreach(v) - 1. For better accuracy, repeat several times and take a median of means at each vertex.