1. For an undirected graph G = (V, E), a dominating set is a subset S ⊆ V such that for each vertex v ∈ V, v ∈ S or a neighbor u of v is in S. Prove that the dominating set problem DS (G, k) such that the graph C contains a dominating set S of size at most k is NP-complete.
2. We say that a problem (a language) L1 ⊆ A* is a linear-time reducible to problem (a language) L2 ⊆ B* (written L1 < L2) if there exists a linear-time computable function φ: A* → B* such that for all α1 α ∈ L1, if and only if φ(α) ∈ L2.
Suppose we know L1 < L2 (i.e., L1 is linear-time reducible to L2) and L2 < L3. Assume that, the time complexity of L2 is θ(n logn).
(a) What we can say about the time complexity of L1? Justify your answer.
(b) What we can say about the time complexity of L3? Justify your answer.
3. Define the class P and the class NP (try to use own words, if possible).
4. Given a table T with m columns and n rows filled with 0's and l's such that each row has at least one 1, and an integer k such that 1 < k < m. The decision problem is to find whether it is possible to choose k columns in T such that each row has at least one 1 at the intersection with the considered columns. Prove that the above decision problem is NP-complete.
5. Prove that the set cover problem U, F is NP-complete, even if for each element from U we have at most two subsets from the family F that cover this element.
6. For a set cover problem U, F construct a cover using greedy algorithm:
U = {1,2,3,4,5,6, 7}, F= {S1, S2, S3, S4, S5},
S1= (1,2,7), S2 = (3, 4, 7), S3 = (5, 6), S4 = (1, 3, 5), S5 = (2,4).
7. Find the cardinality of a maximum independent set of the following tree using dynamic programming algorithm.
