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.



Number of paths equal less than equal to a certain length
The problem is and is not NP-hard. If the length of the input is defined by writing the weights in binary, then it is indeed NP-hard and in fact #P-complete. Say that the target weight $W$ is written in base 10. Suppose further that the graph is a string, as in Reid's construction, with two edges from $i$ to $i+1$, one weight 0 and the other with weight some integer in base 10 with only 0s and 1s in its digits. Also, choose all of the weights so that they cannot add together with any carries. Then the $k$th digit $d$ of the target weight $W$ is a Boolean clause, which says that of those edges that have a non-zero $k$th digit, exactly $d$ are used used. It is not hard to build general Boolean circuits with these clauses.


Also, to clarify a couple of points about this: You can convert from weight at most $W$ to weight exactly $W$ by subtracting off weight at most $W-1$; so in this quick argument it is only #P-hard with a Turing reduction and not a Cook reduction. And of course I'm really showing that the knapsack counting problem is #P-hard.


On the other hand, if the length is defined by writing the weights in unary, to favor small integer values of the weights, then the dynamic programming algorithm given in the question is polynomial time.


Which complexity model is more appropriate depends on the context of the problem, which was not given.


