Longest path in a DAG that's not too long The problem I am interested in is a simple variant of the longest path problem on DAGs: find a path between two chosen vertices in a DAG such that the sum of the weights of its constituent edges is maximized, subject to the constraint that the sum of the weights is less than or equal to some upper bound W. Hence the title of this post, that the longest path not be "too long".

I am aware that the general longest-path problem is NP-Hard, and that the standard longest-path problem on DAGs is easily solved in O(|V|+|E|) time using topological sort and edge-relaxation (i.e. DP) (or we can solve this as shortest path by negating edge-weights).

I've frustratingly searched for a while on the web and came up with nothing on this problem; one would think that so simple a variant would at least be mentioned somewhere (if even in the general case, not limited to DAGs; or perhaps phrased as a shortest path problem where the path shouldn't be "too short"). 

I thought perhaps simply modifying the edge-relaxation condition to include the upper-bound constraint would do the trick, but I realized this is flawed: a "heavier" path may look attractive at the moment, but may end up violating the constraint (and so we should've stuck with the previous, albeit "lighter" estimate). I've not been able to find some alternative way of modifying the DP method to make this go through.

Efficient solutions are appreciated, or, conversely, a proof that this problem is hard. Relevant sources or references would also be appreciated.
This is NP-hard by reduction from subset sum. ​ ​ ​ There is a vertex for each element of the

set and one more vertex. ​ ​ ​ The extra vertex has an outgoing edge to each other vertex

but no incoming edges, and otherwise there is an edge from x to y if and only if ​ x &lt; y .

The weight of each edge is equal to that edge's terminal vertex.

However, one can topologically sort the vertices and then use dynamic programming

in a way that's similar to the dynamic programming algorithm for subset sum.