Hitting set. Consider a set A $=\{$a$1,...,$ an$\}$ and a collection B$1,...,$ Bm of subsets of A$($i$.$e$.,$ Bi A for all i$).$ We say that H A is a hitting set for the collection if H contains at least oneelement from each Bi$,$ that is H Biis non$-$empty for all i $($so H hits all the sets Bi$).$The Hitting$-$Set problem is the following: Given a set A $=\{$a$1,...,$ an$\},$ subsets B$1,...,$ Bm A$,$ and anumber k$,$ is there a hitting set H A of size at most k$?$