Consider the following problem:

Input: An undirected graph $G = (V, E)$, each edge has a non-negative weight $w_i$ and a non-negative value $v_i$. There are two vertices to represent start point $s$ and end point $t$. We are also given two values $W,V$.

Decide whether there is a simple path from $s$ to $t$ with total weight at most $W$ and total value at most $V$.

How do I show that the problem is NP-hard by reduction from PARTITION?

  • $\begingroup$ What did you try? Consider encoding the decision to put an item in one or another part by different choices of arcs in an st-path. $\endgroup$ – Marcus Ritt May 28 '19 at 1:59
  • $\begingroup$ I have tried to construct a complete graph, so that I can represent every combination of choices of integers, but since both constraints are at most, this graph will return a yes instance even if the partition instance is no $\endgroup$ – Deangelo Kingwell May 28 '19 at 3:49
  • $\begingroup$ Make the graph more restricted. Try to do the reduction first for a single item, then for two. $\endgroup$ – Marcus Ritt May 28 '19 at 11:53

Here is the idea of the reduction; I'll let you fill in the details.

We are given an instance of the partition problem, consisting of numbers $x_1,\ldots,x_n$ summing to $S$. We construct a (non-simple) graph on the vertex set $s = v_0,\ldots,v_n = t$. For $i=1,\ldots,n$, there are two edges from $v_{i-1}$ to $v_i$: one with weight $x_i$ and value $0$, and one with weight $0$ and value $x_i$. Our target weight and value are both $S/2$.

I'll let you figure out why this works, and convert it to a simple graph.

  • $\begingroup$ We can simply divide $v_i$ to $v_i$ and $v_i'$. Then, the edges from $v_{i-1}$ to $v_i$ and $v_i'$ should be $x_i\;/\;0$, and edges from $v_{i-1}'$ to $v_i$ and $v_i'$ should be $0\;/\;x_i$. $\endgroup$ – Deangelo Kingwell May 28 '19 at 16:18
  • $\begingroup$ Right, that's the idea. $\endgroup$ – Yuval Filmus May 28 '19 at 16:23

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.