Description
Q1. Assume that a problem A cannot be solved in O(n2) time. However, we can transform A into a problem B in O(n2 logn) time, and then solve B, and finally transform the solution of B in O(n) time into a solution for A.
Prove or Disprove: The above approach shows that B cannot be solved asymptotically less than O(n2) time.
Q2. Prove that Minimum Vertex Cover problem is NP-hard by reducing the NP-hard problem Maximum Independent Set.
Q3. Since finding a minimum vertex cover in a graph is known to be NP-hard, we want to find a vertex cover S that is not too large than a minimum vertex cover. We propose the following algorithm.
Step 1. Initialize S with an empty set.
Step 2. While there is an edge in G, randomly choose an edge (a,b) and insert a and b into S. Then delete the vertices a and b, and all the edges incident to a and b.
Step 3. Return S
Prove that the size of the set S returned by the algorithm can be at most twice the size of a minimum vertex cover of G.
Q4. You are give a social network of n students, where two students are connected if and only if they are friends. Consider the problem of finding a smallest set S of students from the network such that any student in the network is either in S, or a friend of someone who belongs to S.
Either give a polynomial-time algorithm for the problem, or show that the problem is NPhard by reducing the Minimum Vertex Cover problem.
