CODEWITHSUNDEEP
algorithmnp-completereduction
parsa rastegari
parsa rastegari

Reputation: 79

Proving NP-Completeness of a problem

We are given a set A = {a1,a2,...,an}

Given subsets of A named B1,B2, ..., Bm. 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.

Upvotes: 3

Views: 1268

Answers (1)

Nikita Rybak
Nikita Rybak

Reputation: 68006

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

Upvotes: 3

Related Questions