0
$\begingroup$

Let $G=(V,A)$ represent a directed acyclic graph, where a value $v_i \ge 0$ is assigned to every vertex $u_i$. Let $T$ represent a threshold and $N = |V|$. Problem statement:

maximize: $\sum_{i=1}^{N}v_i x_i$

subject to: $\sum_{i=1}^{N} x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

and $x_i(x_j-1) = 0 \quad \forall a\in A: u_i \to u_j$

In other words, we want to choose up to $T$ vertices that maximize the sum of their values, with the restriction that if a vertex $u_i$ is chosen, any reachable vertices $u_j$ must also be chosen. Therefore, $x_i(x_j-1) = 0$ for a given arc $u_i \to u_j$ represents that if $u_i$ is chosen ($x_i = 1$) then $u_j$ must be chosen as well ($x_j = 1$).

I want to prove that this is a NP-hard problem. To do that, I have taken the 0-1 knapsack problem, which is NP-hard:

maximize: $\sum_{i=1}^{M}v_i x_i$

subject to: $\sum_{i=1}^{M} w_i x_i \leq T$ and $x_i \in \lbrace 0,1 \rbrace$

The 0-1 knapsack may be reduced to an instance of the original problem. Assume an instance of the original problem, with the following properties of $G$:

  • $v_i = 0$ for every vertex $u_i$ with incoming arcs.
  • All vertices have at most 1 incoming arc.

The 0-1 knapsack may be reduced to this instance by the following polynomial transformation:

  • There are $M$ items, where $M$ is the number of vertices $u_i \in G: v_i > 0$.
  • The value $v_i$ of each item the value $v_i$ of vertex $u_i$.
  • The weight $w_i$ of each item is $1+$ the number of reachable vertices from $u_i$.

Explanation:

  • Since vertices with a non-zero value have no incoming arcs, they may be chosen independently, as there is no possibility for such a vertice to be chosen twice, as a "dependency" of another one. Thus, individual items in the knapsack problem may be mapped to these vertices.
  • As no vertice has more than 1 incoming arc, no vertice may be reached by multiple vertices. This guarantees that the weights of each knapsack item are independent of each other.

Questions

  1. Have I formulated the original problem correctly, using the mathematical notations? It's been quite some time since I have formally formulated a graph theory problem.
  2. Is this reduction enough to prove that the original problem is NP-hard? I only have reduced the 0-1 knapsack only to an instance of the original problem, not the original problem itself. Does this imply that the original problem is "at least as hard, if not harder" than the 0-1 knapsack?
  3. Assuming that question (2) stands, is my reduction correct?
  4. Alternatively, could I demonstrate my case via another reduction?
$\endgroup$
-1
$\begingroup$

$x_i \leq x_j \forall (i,j) \in A$ is a linear constraint that represents your requirement (if $x_i=1$ it would push $x_j$ to take value $1$ as well). You get a constrained knapsack problem. You can easily reduce a knapsack to it by considering a graph that simply has no arrows.

$\endgroup$
  • $\begingroup$ A graph with no arcs can be solved in $\mathcal{O}(N)$, as it's enough to find the $T^{th}$ "heaviest" vertex and choose this and all heavier ones. It's essentially the 0-1 knapsack with all weights being $w_i = 1$. Note that the "weight" in the original problem is the number of "dependent" vertices that have to be chosen, as well. Am I missing something? (Thanks for the notation) $\endgroup$ – Adama Nov 6 '17 at 17:24
  • $\begingroup$ I don't think your idea for a reduction works. Knapsack has both value and weight for each item; this problem has only value, but no weight. I don't see how you propose to encode the weights of the items in the knapsack problem. If you think the reduction works, I encourage you to edit the answer to show the proposed reduction explicitly. (Cc: @Adama -- no, I don't think you're missing anything.) $\endgroup$ – D.W. Feb 6 '18 at 21:44

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.