Fast algorithm for counting the number of acyclic paths on a directed graph?

This is #P-complete, it seems. (ref maths.uq.edu.au/~kroese/ps/robkro_rev.pdf ). The link has an approximation If you can relax the simple path requirement, you can efficiently count the number of paths using a modified version of Floyd-Warshall or graph exponentiation as well.

See All pairs all paths on a graph.

This is #P-complete, it seems. (ref maths.uq.edu.au/~kroese/ps/robkro_rev.pdf). The link has an approximation If you can relax the simple path requirement, you can efficiently count the number of paths using a modified version of Floyd-Warshall or graph exponentiation as well.

See All pairs all paths on a graph....

Just to clarify --- it's not an approximation algorithm (i.e. Algorithm that would have a known bound on error) but a stochastic algorithm that provides a statistical estimate. The original question asks about a Monte Carlo approach, which is provided in your reference, so maybe it's good to highlight that.

– antti. Huima Apr 6 at 17:03 @antii - you're right, thanks for the clarification – spinning_plate Apr 6 at 17:35.

As mentioned by spinning_plate, this problem is #P-complete so start looking for your aproximations :). I really like the #P-completeness proof for this problem, so I'd think it would be nice to share it: Let N be the number of paths (starting at s) in the graph and p_k be the number of paths of length k. We have: N = p_1 + p_2 + ... + p_n Now build a second graph by changing every edge to a pair of paralel edges.

For each path of length k there will now be k^2 paths so: N_2 = p_1*2 + p_2*4 + ... + p_n*(2^n) Repeating this process, but with I edges instead of 2, up n, would give us a linear system (with a Vandermonde matrix) allowing us to find p_1, ..., p_n. N_i = p_1*i + p_2*(i^2) + ... Therefore, finding the number of paths in the graph is just as hard as finding the number of paths of a certain length. In particular, p_n is the number of Hamiltonian Paths (starting at s), a bona-fide #P-complete problem.

I havent done the math I'd also guess that a similar process should be able to prove that just calculating average length is also hard. Note: most times this problem is discussed the paths start from a single edge and stop wherever. This is the opposite from your problem, but you they should be equivalent by just reversing all the edges.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.