2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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
    Commented May 28, 2019 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
    Commented May 28, 2019 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
    Commented May 28, 2019 at 11:53

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented May 28, 2019 at 16:18
  • $\begingroup$ Right, that's the idea. $\endgroup$
    – Yuval Filmus
    Commented May 28, 2019 at 16:23

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.