# Existence of path under weight and value budgets

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?

• 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. – Marcus Ritt May 28 '19 at 1:59
• 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 – Deangelo Kingwell May 28 '19 at 3:49
• Make the graph more restricted. Try to do the reduction first for a single item, then for two. – Marcus Ritt May 28 '19 at 11:53

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$$.
• 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$. – Deangelo Kingwell May 28 '19 at 16:18