## Description

Q1. Assume that a problem A cannot be solved in O(n

2

) time. However, we can transform

A into a problem B in O(n

2

log n) 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

2

) 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.

1