Number of paths equal less than equal to a certain length

Question

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.

Answer 1

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.

Answer 2

This problem seems to be NP-hard, in an informal sense. I'll sketch how we could use an algorithm for this problem to solve the knapsack problem. Suppose given $n$ objects with weights $w_1$, ..., $w_n$; the problem is to determine whether we can find $k$ of the objects with total weight at most $W$.

Build a directed acyclic graph with $n+1$ vertices labeled $v_0$, ..., $v_n$. From $v_{i-1}$ to $v_i$ put one edge of weight 0 and $t$ edges of weight $w_i$. Here $t$ is a parameter which will vary. Use our algorithm to compute the number of paths of total weight at most $W$ from $v_0$ to $v_n$ in this graph. This number is $N(t) = \sum_{j=0}^n x_j t^j$, where $x_j$ is the number of ways to choose $j$ of the numbers $w_1$, ..., $w_n$ summing to at most $W$. Perform this for $t = 0$, ..., $n$. The degree-$n$ polynomial $N(t)$ is determined by its values at these $n+1$ values of $t$, so using standard linear algebra we can compute the coefficients of $N(t)$. In particular, we can compute whether $x_k > 0$.

Answer 3

Unlike the previous shortest-path counting question this one is at least NP-hard (I would guess #P-hard but I don't have a reference at hand for that): see Donald B. Johnson and Samuel D. Kashdan, Lower bounds for selection in $X+Y$ and other multisets, JACM 25: 556–570, 1978.