Hey,

I need to count the number of paths from node $s$ to $t$ in a weighted directed acyclic graph s.t. the total weight of each path is less than or equal to a certain weight $W$. I have an algorithm to do it in $O(nW)$ using dynamic programming. Let $N_W(s,t)$ denote the number of such paths (with weight less than $W$) from $s$ to $t$.

It seems like doing it in polynomial time would be hard, since for instance if I take the strategy of calculating $N_W(s,u)$ for $u$ in the paths between $s,t$, then I would have to keep track of how many paths are there from $s\rightarrow p,p\in parents(u)$ for every weight in $\{1,\dots,W\}$ which alone would take $O(nW)$ time and space.

So my question is what is the complexity of this problem?

Thanks

Edit: Changed $O(W)$ to $O(nW)$ for the running time of the dynamic programming approach. Correction thanks to David Eppstein.