Skip to main content
3 of 3
Commonmark migration

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?