The Weight-Length problem is defined as follows: Let G(V,E) be a directed graph with a non-negative weight function w(e) and a non-negative integer length function l(e). Given a non-negative number W and non-negative integer L and nodes s and t, determine whether there's an s->t path of weight at most W and length at most L.
a. Give an efficient dynamic programming algorithm that is polynomial in L, |V |, and |E| to solve this problem. Hint: Consider a generalization of Bellman-Ford.
b. Show that this problem is NP-complete using a reduction from Partition. Hint: Given an array {a1, . . . , an}, create a graph with n + 1 vertices arranged in a line with two parallel edges from each vi to vi+1. Add appropriate weights and lengths and choose s, t, W, L.