2 replaced http://cstheory.stackexchange.com/ with https://cstheory.stackexchange.com/ edited Apr 13 '17 at 12:32 If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $$O(VE)$$. For dense graphs, you can build an algorithm whose running time is $$O(V^\omega)$$, where $$\omega$$ is the exponent for fast matrix multiplication ($$\omega \approx 2.8$$ in practice). If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider. If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $$O(VE)$$. For dense graphs, you can build an algorithm whose running time is $$O(V^\omega)$$, where $$\omega$$ is the exponent for fast matrix multiplication ($$\omega \approx 2.8$$ in practice). If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider. If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $$O(VE)$$. For dense graphs, you can build an algorithm whose running time is $$O(V^\omega)$$, where $$\omega$$ is the exponent for fast matrix multiplication ($$\omega \approx 2.8$$ in practice). If the original value of the counts can be different from 1, then your problem is https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider. 1 answered Feb 21 '17 at 0:21 D.W.♦ 105k1414 gold badges133133 silver badges309309 bronze badges If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in http://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $$O(VE)$$. For dense graphs, you can build an algorithm whose running time is $$O(V^\omega)$$, where $$\omega$$ is the exponent for fast matrix multiplication ($$\omega \approx 2.8$$ in practice). If the original value of the counts can be different from 1, then your problem is http://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.