The assignment is deliberately short, try to submit it sooner to leave enough time for preparation for the final exam. Q1 [50 marks]. A decision version of interval scheduling would be: given a collection of intervals and an an integer k, is there a subset of non-overlapping intervals of size at least k? Answer the following questions with yes, no or unknown, with a brief explanation 1. Interval Scheduling ≤ P Vertex Cover? 2. Independent Set ≤ P Interval Scheduling? Q2 [50 marks]. Given a graph G and two nodes a and t , consider the following two questions : A) What is the length of the shortest path from s → t? B) What is the length of the longest path from s → t? Recall that the theory of np-completeness applies to decision problems, not optimization problems (although they are related as explained in the class): 1. Formulate A to a decision problem (a problem with a yes/no answer), call it AD 2. Formulate B to a decision problem (a problem with a yes/no answer), call it BD Analyze the np-completeness of the problems and answer the following questions with (yes,no or unknown), with a brief explanation 3. AD is P 4. AD is NP 5. AD is NP-Complete 6. AD is NP-Hard 7. BD is P 8. BD is NP 9. BD is NP-Complete 10. BD is NP-Hard
