I have the following problem, and would like to figure out whether or not it's NP-hard - primarily to know that searching for a polynomial algorithm for it is futile. Approximations are possible, and in practice sufficient, but I'm still interested in how hard the exact problem is.

Given is a DAG $(V, E)$, where every vertex $x$ is labeled with a weight $w_x$ (a strictly positive integer) and a value $v_x$ (an integer), and the edges indicate dependencies between the vertices. The goal is finding the non-empty subset $S \subset V$ of vertices with the highest average value/weight ratio $$f(S) = \frac{\sum_{x \in S} v_x}{\sum_{x \in S} w_x}$$ under the constraint that the subset $S$ must respect dependencies: $$x \in S \implies y \in S \quad \text{for all}\, (x,y) \in E$$ If there are multiple subsets with identical maximal $f(S)$ it does not matter which one is found.

In some ways it feels similar to a knapsack problem, but instead of having a fixed weight limit and only optimizing for maximal value, here every new element added to the selection just increases the overall denominator. This makes the problem very easy if it weren't for the dependencies (return the singleton with the highest individual value/weight ratio).

To turn it into a decision problem, I'd imagine that the problem gets turned into "does a dependency-respecting subset $S$ with ratio $f(S) \geq r$ exist?", where $r$ could be an integer (if one is interested in a fractional ratio, all values $v_x$ can be multiplied with its denominator instead). This problem is clearly in NP.

It can be assumed that the graph is connected when ignoring direction, because there is always at least one highest-ratio subset that does not span connected components, and thus the problem can be solved per component. My guess is that assuming $w_x = 1$ for all $x$ doesn't change the complexity, though I have no proof for that (it's possible to turn a node with weight $w_x = k$ into $k$ nodes with weight 1, but unless the weights are given in unary this means adding an exponential number of nodes).

I'm happy to hear any insights, pointers to existing work, or approaches for proofs.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.