The Hitting Set Problem is NP-complete. To recap the definitions, consider a set

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.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.