Question 1. Algorithm Design by Kleinberg and Tardos.
In Exercise 5 of Chapter 8, we claimed that the Hitting Set Problem was NP-complete. To recap the definitions, consider a set A = {a 1 , . . . , a n } and a collection B 1 , B 2 , . . . , B m of subsets of A. We say that a set H ⊆ A is a hitting set for the collection B1, B2 , . . . , Bm if H contains at least one element from each B i -that is, if H ∩ B i is not empty for each i. (So H "hits" all the sets B i .)
Now suppose we are given an instance of this problem, and we'd like to determine whether there is a hitting set for the collection of size at most k. Furthermore suppose that each set B i has at most c elements, for a constant c. Give an algorithm that solves this problem with a running time of the form O(f (c, k) • p(n, m)), where p(•) is a polynomial function, and f (•) is an arbitrary function that depends only on c and k, not on n or m.
Question 2. (Algorithm Design by Kleinberg and Tardos.)
The Minimum-Cost Dominating Set Problem is specified by an undirected graph G = (V , E) and costs c(v) on the nodes v ∈ V. A subset S ⊂ V is said to be a dominating set if all nodes u ∈ V -S have an edge (u, v) to a node v in S. (Note the difference between dominating sets and vertex covers: in a dominating set, it is fine to have an edge (u, v) with neither u nor v in the set S as long as both u and v have neighbors in S.)
(a) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G is a tree.
(b) Give a polynomial-time algorithm for the Dominating Set Problem for the special case in which G has tree-width 2, and we are also given a tree decomposition of G with width 2.
Hints:-
Hint:
1. Problem 1 - refers to the example in 10.1 Small vertex cover set problem. Example: A={a, b, c, d, e, f, g} B1={a,b}, B2=(a, c, d, e}, B3=(c, f, g} H1={a, c} is a hitting set for B1, B2 and B3.
H2={b, c, f} and H3={a,b, c, d, g} are also hitting sets.
The problem is to identify if there is a hitting set of size at most k. In this example, the answer is yes for k=2, and the answer is no for k=1.
2. For Problem 5, refers to Section 10.2, the Maximum-Weight Independent Set Problem on a Tree. Noted the difference between Dominate Set and Vertex Cover Set. Hence, for a no-leaf node u, if u is in, its children can be either in or out; if u is out, then one of the two following cases must be true: a. u's parent node is in ; b. at least one of u's children nodes is in.
Requirements:-
- Problem A: Create an application scenario where the problem can be formulated as Maximum- Weight Independent Set Problem on a Tree. Use a small problem instance of this application problem as input to illustrate how th algorithm described in Section 10.2 works and show the solution.
Requirement
When present an algorithm:
1. First describe the overall idea of the algorithm using English language.
2. Then present the algorithm details using pseudo code, be clear of the meaning of each variable, with comments on important steps to explain its purpose.
3. Must walk through the algorithm step by step with a small problem instance to show how the algorithm works. (Required, unless you have implemented the algorithm and show the output instead).
4. Analyze time complexity of algorithm and present results in big-O notation.