COMP 400 ASSIGNMENT 5
Due August 2, 19:59 CST
General Instruction: In solving these questions you may consult books or notes, but you may not consult with each other. Students who are found cheating will automatically receive a 0 grade for this assignment and will be reported as a case of academic offense.
There are in total 36 points, but your grade will be considered out of 30.
You should send the pdf file (either typed, or a clear and readable scan) of your solution to the admin email: cs400summer2020@sina.com.
Question 15 (5 marks)
Consider the Triangle Removal problem.
We are given an undirected graph G = (V, E), and an integer k, is it possible to find a set of vertices U ⊆ V where |U | ≤ k such that deleting these vertices removes all the triangles (i.e. cycles of length 3) from the graph. Prove that
Question 17 (14 marks)
For each of the two questions below, decide whether the answer is (i) “Yes,” (ii)“No,” or (iii) “Unknown, because it would resolve the question of whether P = NP.” Give a brief explanation of your answer.
• Recall the Interval Scheduling Problem from COMP 271: Given a collec- tion of intervals on a timeline, and a bound k, does the collection contain a subset of non overlapping intervals of size at least k? Can we have Interval Scheduling ≤p Vertex Cover.
• Is it the case that 3-COL ≤p Interval Scheduling?
Question 18 (9 Marks)
The PARTITION problem is defined as follows: you are given a set of n po- sitive numbers x1, . . . , xn, and you have to decide if they can be partitioned into two sets S1 and S2 such that the sum of numbers in each of the two sets are equal. Prove that PARTITION is NP-complete.
Question 19 (6 Marks)
Prove that the following problem belongs to P: Given a graph G, we want to know whether G has an independent set of size 100.
Question 20 (7 Marks)
Consider the Triangle Removal Problem from Question 15. Prove that Trian- gle Removal Problem is NP-complete. You may assume that we have com- pleted showing Triangle Removal Problem is in NP.