Exercise 3 Consider a graph G = (V, E). An independent set of the graph G is a set of vertices SV such that for all x, y S the x,y is not an edge of the graph G. A set DX is said to be a dominating set if for every x X /D there exists y D such that xy E.

it is a Dominating and Independent sets (DIS) problem

Instance : A graph G = (V, E) and an integer k (1,|X|].

Question :

1. Are there a dominating set of size k and an independent set of size k

2. Show that DIS is in NP?

3. Show that DIS is NP-Hard? Hint: Maximal independent set.

3. Suppose that P= NP and given a polynomial-time black-box algorithm for solving the decision problem DIS. Give a polynomial-time algorithm to solve the associated optimization problem.