Problem Set 7—NP Completeness

Purpose

This problem set develops your ability to prove problems to be NP complete.

Background

This problem set is mainly based on material covered in section 34.5 of our textbook. We covered this material in classes on November 24 and December 3.

Activity

Solve each of the following problems.

Problem 1

Exercise 34.5-1 in our textbook (subgraph isomorphism).

Problem 2

Exercise 34.5-2 in our textbook (0-1 integer programming). The “≤” comparison between two vectors in the problem description is an element-by-element comparison, i.e., a ≤ b iff a and b are the same length and a_i ≤ b_i for all positions i.

Problem 3

Exercise 34.5-3 in our textbook (integer linear programming).

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. If you worked in a group on this exercise, the whole group should schedule a single meeting with me. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.