Consider the following problem:

Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer. Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a subset $AS$ of $A$ so that the weight of $AS$ is less than $W$ and the value of $AS$ (the sum of the value of its items) is maximized is the 0/1 Knapsack Problem

Now, consider a deviation from it where the items in $A$ have certain dependency relationships between each other, and these dependencies can be captured by a directed acyclic graph $G(A, E)$. The value of the set $AS$ is no longer the sum of the value of the items in $AS$. For each item in $AS$, its value depends on which other items are also in $AS$. More formally, if $v$ is in $AS$, its contribution to the value of $AS$ would be its own value, plus the value of all the ancestors of $v$ in $G$ not in $AS$.

My Questions

What is the complexity of this problem? Is it NP-Hard in the strongest sense or in the weak sense? (in the strongest sense (one for which no pseudo-polynomial algorithm is known)). I have tried to come up with a modification of the classic dynamic programming algorithm to solve it, but with no luck. I am thinking that I should try to reduce an NP-Hard problem for which no pseudo-polynomial time algorithm is known to this problem. Do you know any of such problems that looks similar to this one?

  • 1
    $\begingroup$ Most probably 0/1 knapsack is a special case of your problem (when there are no dependencies), and this would imply that your problem is NP-hard, and so NP-complete (since it is clearly in NP). What you are really asking is, what is the complexity of this problem when weights are encoded in unary. $\endgroup$ – Yuval Filmus Apr 21 '15 at 2:55
  • $\begingroup$ Yes, but Knapsack is an NP-Hard problem with a pseudo-polynomial solution. Could it be that this problem is an NP-Hard problem that most likely does not have a pseudo-polynomial solution? To answer that question I would need to reduce an NP-Hard problem for which no pseudo polynomial solution is known to my problem, but I am having a hard time finding such problem. $\endgroup$ – ASDF Apr 21 '15 at 12:53
  • $\begingroup$ Let me repeat again my comment. You are interested in the complexity of your problem when the weights are encoded in unary. If this problem is in P, then your problem has a pseudopolynomial solution. Otherwise it doesn't. $\endgroup$ – Yuval Filmus Apr 21 '15 at 14:43
  • $\begingroup$ Got it now. Thanks for the clarification. $\endgroup$ – ASDF Apr 21 '15 at 15:17
  • $\begingroup$ Since I don't know what the answer is, I need to attack the problem from both fronts: start looking for a polynomial solution with weights encoded in unary and on the other hand start looking for a reduction from an NP-Hard problem not in P (likely not in P). $\endgroup$ – ASDF Apr 21 '15 at 17:08

Your Answer

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

Browse other questions tagged or ask your own question.