Skip to main content
Computer Science

Return to Question

Commonmark migration
Source Link
Community Bot
Community Bot
  • 1

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?

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?

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?

deleted 1 character in body; edited tags; edited title
Source Link
Yuval Filmus
Yuval Filmus
  • 279.1k
  • 27
  • 316
  • 512

Partition problem reduction Existence of path under weight and value budgets

Suppose I have an algorithm: An undirected graph G = (V, E), each edge has a non-negative weight wi and a non-negative value vi. There are two vertices to represent start point s and end point t. We are also given the upper bound of total weight W and total value V. Decide whether there is a simple path from s to t withConsider the total weight at most W and total value at most V.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 to reduce partition problem to thisdo I show that the problem is NP-hard by reduction from PARTITION?

Partition problem reduction

Suppose I have an algorithm: An undirected graph G = (V, E), each edge has a non-negative weight wi and a non-negative value vi. There are two vertices to represent start point s and end point t. We are also given the upper bound of total weight W and total value V. Decide whether there is a simple path from s to t with the total weight at most W and total value at most V.

How to reduce partition problem to this problem

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?

Source Link
Deangelo Kingwell
Deangelo Kingwell
  • 23
  • 2

Partition problem reduction

Suppose I have an algorithm: An undirected graph G = (V, E), each edge has a non-negative weight wi and a non-negative value vi. There are two vertices to represent start point s and end point t. We are also given the upper bound of total weight W and total value V. Decide whether there is a simple path from s to t with the total weight at most W and total value at most V.

How to reduce partition problem to this problem