3
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Sep 13, 2019 at 18:32
  • $\begingroup$ 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 ! $\endgroup$
    – Farah Mind
    Sep 13, 2019 at 19:04
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Sep 13, 2019 at 21:47
  • $\begingroup$ 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! $\endgroup$
    – Farah Mind
    Sep 13, 2019 at 22:22
  • $\begingroup$ It is not NP-hard to search for a path of length $K$, if $K$ is a constant. $\endgroup$
    – xskxzr
    Sep 14, 2019 at 3:21

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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