Question

Consider the following four problems:
Bin Packing: Given n items with positive integer sizes s1,s2,...,sn, a capacity C for bins and a positive integer k, is it possible to pack the n items using at most k bins?
Partition: Given a set S of n integers, is it possible to partition S into two subsets S1 and S2 so that the sum of the integers in S1 is equal to the sum of the integers in S2? Longest Path: Given an edge-weighted digraph G = (V,E), two vertices s,t ∈ V and a positive integer c, is there a simple path in G from s to t of length c or more? Shortest Path: Given an edge-weighted digraph G = (V,E), two vertices s,t ∈ V and a positive integer c, is there a simple path in G from s to t of length c or less?
1. Briefly explain the terms certificate, certifier, NP, and NP-completeness.
2. Classify (with justification) which of the following are yes or no instances to the Bin Packing problem.

• Sizes 1,2,2,3,4, capacity 4, bins 3.

• Sizes 1,1,1,2,2,2,3,4,4,4, capacity 4, bins 5.

• Sizes 1,2,2,2,4,5,5,7,8,8,8,9,9,10, capacity 20, bins 4.

• Sizes 4,6,7,19,21,22,25,39,57,58,69,70, capacity 100, bins 4

• Sizes 1,1,1,1,1,2,3,4,4,5,6,6,6,6,7,9,10,13,17,17,19,20,20,23, capacity 101, bins 2. 3.

Show that Partition ≤p Bin Packing. 4. Is the problem Longest Path NP-complete when restricted to directed acyclic graphs? Prove your answer.

5. Show that Longest Path≤p Shortest Path, where we allow negative edge weights (and possibly cycles of negative weight). Does this show Shortest Path is NP-complete? Explain.

Answer 1