Proving NP-Completeness of a problem

Question

We are given a set A = {a₁,a₂,...,a_n}

Given subsets of A named B₁,B₂, ..., B_m. If a subset of A named H has intersection with all given B's, we call H "Covering subset". Is there any "covering subset" of size K (cardinality of H is K) for given A and Bs? Prove that this problem is NP-Complete.

We should reduce some known problem to "covering subset" problem.

Answer 1

update This is called a hitting set. You can read the same answer in wikipedia article.

This problem is, in a way, dual to set cover problem.

We'll change some terminology. Let {B1, B2, ...} be elements and {a1, a2, ...} be sets. 'Set' ai contains 'element' Bj in a new problem if set Bj contains ai in original problem.

Now, you just need to select minimum number of 'sets' ai covering all 'elements' Bj. And that problem is NP-complete, as shown in the link above.

To clarify the transformation, one problem definition can be produced from another just by replacing set/element and contains/contained. Compare following

Every set Bj contains some selected element ai
Every 'element' Bj is contained by some selected 'set' ai