[Solved] CMPT360 Assignment 5

Q1. Assume that a problem A cannot be solved in O(n²) time. However, we can transform A into a problem B in O(n² 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(n²) 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.