Longest path in a DAG that's not too long
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.