Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
By the way, your dynamic programming approach is I think O(nW), not O(W). And it can be slightly improved to O(nΔ) where Δ is the difference between W and the shortest path length. –  David Eppstein Nov 9 '09 at 18:11
add comment

3 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

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$.

share|improve this answer
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.