System of nondistinct representatives efficiently solvable?

Question

We have sets S₁, S₂, ..., S_n. These sets do not have to be disjoint. Our task is to select a representative member for each set, such that the total number of elements selected is as small as possible. One element may be present in more than one set, and can represent all the sets it is included in. Is there an algorithm to solve this efficiently?

Answer 1

It is easier to answer this question after restatement: let the original sets S₁, S₂, ..., S_n be elements of the universe and let the original set members be sets themselves: T₁, T₂, ..., T_m (where T_i contains elements {S_j} which are the original sets containing corresponding member).

Now we have to cover universe S₁, S₂, ..., S_n with sets T₁, T₂, ..., T_m. Which is exactly Set cover problem. It is a well known NP-hard problem, so there is no algorithm to solve it efficiently (unless P=NP, as theorists usually say). As you can see from Wikipedia page, there is a greedy approximation algorithm; it is efficient, but approximation ratio is not very good.

Answer 2

I'm assuming that by "efficiently," you mean in polynomial time.

Evgeny Kluev is correct, the problem is NP-hard. The decision version of it is known as the hitting set problem and was shown to be what we now call NP-complete soon after the introduction of that concept. While it's true that Evgeny's reduction is from the hitting set problem to the set cover problem, it's not hard to see an explicit inverse reduction.

Given a set C={C₁,C₂,...C_m} whose union is U={u₁,u₂,...,u_n}, we want to find a minimal-cardinality subset C' whose union is also equal to U. Define S_i in your initial problem as {C_j in C | u_i is an element of C_j}. The minimum hitting set of S={S₁,S₂,...,S_n} is then equal to our desired C'.