Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
EECS 340/454: Algorithms
Assignment 8 (454 Only): NP-Completeness
Problem 1
The Maximum-Disjoint-Subset problem is defined as follows: We are given a collection S of
sets. We would like to find the maximum number of disjoint sets in S.
(a) Formulate the decision version of the Maximum-Disjoint-Subset problem.
(b) Prove that the decision version you formulated in (a) is NP-complete by reduction from
3-CNF-SAT.
Problem 2
Consider the following decision problems:
• 0-1 Knapsack: Given a finite set S of n items, weight function wi : S → Z, value function
vi : S → Z, and two integers W and V , is there a subset C ⊆ S such that
∑
i∈C wi ≤W and∑
i∈C vi ≥ V ?
• Subset-Sum: Given a set R = {b1, b2, ...., bm} of m integers and another integer B, is there
a subset D ⊆ R such that ∑i∈D bi = B?
Given that Subset-Sum is NP-complete, prove that 0-1 Knapsack is NP-Complete.