The Hitting Set Problem is NP-complete. To recap the definitions, consider a set
ID: 3730208 • Letter: T
Question
The Hitting Set Problem is NP-complete. To recap the definitions, consider a set A = {al ..... an} and a collection B1. B2 ..... Bm of subsets of A. We say that a set H _ A is a hi.rig set for the collection BI. B~_ ..... Bm ff H contains at least one element from each B~--that is, ff H n B~ is not empty for each i. (So H "hits" all the sets B~.) Now suppose we are given an instance of t~s 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~ has at most c elements, for a constant c. Give an algorithm that solves this problem with a running time that is exponentially smaller than brute force (i.e O(p(n,m)2n) where p(n,m) is polynomial in n,m) Hint: Try to mimic algorithm for 3-CNFSAT
Explanation / Answer
Proof is given below, please provide a clear image.Though considering all the perameters ,sets and symbol as per the given question the answer is provided.
Answer:
Hitting Set is NP-complete.
Consider a set A = {a1, ..., an} and a collection B1, B2, ..., Bm of subsets of A.
which implies that, Bi A ; i
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 Bi , as if H Bi is not empty for each i. (So H "hits" all the sets Bi.)
suppose we are given an instance of hitting set problem, and we’d like to determine whether there is a hitting set for the collection of size at most k.
First to prove that H i.e Hitting Set is in NP. Now if H is of size k and H Bi where Bi ={B1, . . . , Bm},then it is verified in polynomial time.
Now need to consider an instance for reducing from vertex cover –graph G = (V, E) having a positive integer k.
Where the instance implies that the set A = {a1, ..., an} belongs to the set of V of graph G.
Now suppose that every edge L E where let SL:{a1,a2} that means set SL holding two nodes of L.
So it can be concluded that set of vertices SE has a vertex cover of G where all the elements of H belonging to hitting set instance Bi.
Furthermore suppose that each set Bi has at most c elements, for a constant c for giving an algorithm that solves this problem with a running time that is exponentially smaller than brute force (i.e O(p(n,m)2n) where p(n,m) is polynomial in n,m)
Considering the divide -and-conquer algorithm where A consists of hitting set instance, resulting either hitting set of size k or NO
Now suppose for base case,when k = 1, the algorithm checks whether there is any element belonging to all the sets or not and for k > 1 and t is an instance of hitting set A.
Suppose A implies the set of elements in t where B1, . . . , Bm be the subsets.
The algorithm A choose a subset B1 where the elements in B1 be{ L1, . . . , Lc} as if each set consists of at most c number of elements from where at least one element is been chosen from B1.
An element Li , suppose (t –Li) indicate the instance from where it can be eliminated all sets incorporating Li from t and remaining elements going to be hit.
So it is concluded that for each element Li B1 and the algorithm repeatedly call A for (t – Li) having hitting set size(k–1). If algorithm generates c number of recursive calls.
Another situation where if any recursive calls returns a set SE like( t Li ) then algorithm returns (SE Li) and algorithm returns NO if all recursive calls returns NO
The running time:
So the total number of recursive calls is ck where each recursive calls takes time O(n + m) time to create new instances. Thus running time is O(ck(n + m)), if use brute force for dynamic programming algorithm then this above algorithm exponentially smaller than brute force algorithm where p(n,m) is polynomial in n,m.