2

I'm solving an algorithmic problem and managed to decompose it. Here is the sub problem I have:

I have n sets, let's say {1,2},{2,3},{3,4} I need to find the smallest set that have at least one element in every of these n sets, the solution here is: {2,3}.

It's not a greedy problem, think about {1},{1,3},{1,3,4},{2,3,4},{2,3},{2} the solution is {1,2} even though 3 have the biggest frequency.

Maybe there is also a common name for that algorithm, I tried to search but didn't manage to find anything useful.

Keloo
  • 1,368
  • 1
  • 17
  • 36

1 Answers1

4

This sounds like the minimum vertex cover problem, which is NP-complete.

Let each of the values be a vertex and two vertices are adjacent if they coexist in the same set somewhere. By this construction, any element in any set will be at most distance 1 away from a cover vertex, therefore a minimum vertex cover will cover the sets. Another way to think about it, if a set does not contain a cover vertex, then there must be at least one edge in the set that doesn't include a cover vertex by construction. This contradicts the cover property, however, therefore every set will contain a cover vertex.

kevmo314
  • 4,223
  • 4
  • 32
  • 43