# Algorithm to find a simple path with maximum weight less than a constant in DAG

Given a weighted directed acyclic graph $$G=(V,E,W)$$, where the weights are non-negative and are on the vertices. I am searching for a simple path of maximum total weight, but this total weight should not exceed a given constant $$K$$.

Perhaps my question is elementary but I cannot find any solution. Indeed, it is well known that finding a simple path with maximum weight in $$G$$ is polynomial, but by adding the fact that this total weight should not exceed a given constant $$K$$, will the problem remain polynomial? because we need to keep at each node the set of path lengths that can be reached by the next vertices.

• Have you tried to construct a reduction? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. – D.W. Sep 13 at 18:32
• I though first that it is as hard as the problem of searching a simple path of weight $K$ in DAG, since this later is NP-hard (reduction from the subset sim problem), so the problem of finding a simple path of maximum weight at most $K$ is also NP-hard, but I was not sure especially when I read this post cstheory.stackexchange.com/questions/5430/… where they say that when the weights are all less than a given value than the problem can be solved in polynomial time ! – Farah Mind Sep 13 at 19:04
• Even in the answer given to the question you link to, the algorithm is not necessarily polynomial in the size of the instance if $C$ is a part of the instance description, as $C$ can be coded in $\log_2(C)$ bits and $C$ can thus be exponential in the size of the instance (it is only a pseudo-polynomial-time algorithm). On the other hand, if $K$ is truly a constant independent of the instance, then the algorithm mentioned in that post is also polynomial in your case. – Tassle Sep 13 at 21:47
• yes $K$ is truly a constant, but if at each node we calculate the set of path lengths how the complexity of the algorithm could be $O(nmK)$? On the other hand, do you think that the problem cited above is as hard as searching for a simple path of length $K$? if so this later is NP-hard by a reduction from the subset sum problem! – Farah Mind Sep 13 at 22:22
• It is not NP-hard to search for a path of length $K$, if $K$ is a constant. – xskxzr Sep 14 at 3:21

Since there is no negative weight, you only need to keep at each node the set of path lengths no more than $$K$$. Because $$K$$ is a constant, you only keep a constant number of path lengths at each node. Hence, the algorithm remains polynomial-time.