Reference no: EM133040367

Question 1. Let C(G, k) denote the decision problem of whether the undirected graph G = (V, E) has a subset of vertices V' ⊆ V such that |V'| = k and there is an edge connecting every pair of vertices in V'. Prove that C(G, k) is NP-Complete.

Question 2. Given two graphs H = H(V_H, E_H) and G = G(V_G, E_G), H is a subgraph of G if V_H ⊆ V_G and E_H ⊆ E_G. Let X be the following problem:

INPUT: Two undirected graphs H and G
OUTPUT: Is H a subgraph of G?

Using the NP-completeness of problem C(G, k) from the previous question, show that X is NP-Complete too.

Question 3. Consider the following problem: As input, you are given a list of squares S₁, S₂,......,S_m, in the plane, all distinct from one another. Each square has side-length exactly 2, and the bottom-left corner of each square is located at integer coordinates (x, y) ∈ Z₂.

The goal is to find the largest subset C ⊆ [m] such that for all distinct i, j ∈ C, S_i, and S_j do not intersect. Give a 4-approximation algorithm solving this problem. That is, give an algorithm which outputs a set C of non-overlapping squares such that |C| ≥ 1/4 |C*| where C* is the largest set of non-overlapping squares.

Question 4. Given a set U = {u₁, , u_n}, natural number b, and S₁, ..., S_m, ⊆ U such that |Si| ≤ b for all i = 1,....,m. Also, each element u_i has weight w_ui ≥ 0. We say a set S is a hitting set, if S ∩ S_i ≠ 0 for every i = 1, 2, ..., m. The problem is to find a hitting set H ⊆ U such that the total weight of the elements in H is minimized. Give a b-approximation algorithm solving this problem.

Question 5. Given a set P of n points on the plane, consider the problem of finding the disk with smallest radius containing all the points in P. Provide a √3-approximation algorithm for this problem that runs in time O(n²).