Homework 8 - NP-Completeness



These homework problems are due at the start of class on Thursday, June 4.
We will be going over the hw solutions in class so late homeworks will not be accepted.
  1. Problem 8.14 from [DPV] (Clique + Independent Set)
  2. Problem 8.15 from [DPV] (Max Common Subgraph) ** Can skip proving that it's in NP, just give the reduction
  3. Problem 8.19 from [DPV] (Kite)